强连通缩点— HDU1827

时间:2024-10-03 13:06:20

  强连通缩点以后最终形成的是一棵树

  我们可以根据树的性质来看缩点以后的强连通分量图,就很好理解了

/*  gyt
Live up to every day */
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
#include<set>
#include<string>
#include<map>
#include <time.h>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = +;
const ll maxm = 1e7;
const int modd = ;
const int INF = <<;
const db eps = 1e-;
struct Edge{
int u, v, next;
}e[maxn*];
int n, m, cnt,scnt, tot;
stack<int>sta;
int dfn[maxn], low[maxn], vis[maxn], head[maxn];
int du[maxn], color[maxn];
int a[maxn], in[maxn]; void init() {
memset(head, -, sizeof(head));
memset(dfn, , sizeof(dfn));
memset(low, , sizeof(low));
memset(vis, , sizeof(vis));
memset(du, , sizeof(du));
memset(color, , sizeof(color));
for (int i=; i<maxn; i++) in[i]=INF;
while(!sta.empty()) sta.pop();
cnt=;
scnt=; tot=;
}
void add(int u, int v) {
e[cnt].v=v, e[cnt].next=head[u];
head[u]=cnt++;
}
void Tarjan(int s) {
int minn, t;
dfn[s]=low[s]=++tot;
vis[s]=;
sta.push(s);
for (int i=head[s]; ~i; i=e[i].next) {
int t=e[i].v;
if (!dfn[t]) {
Tarjan(t);
low[s]=min(low[s], low[t]);
} else {
if (vis[t]==) {
low[s]=min(low[s], dfn[t]);
}
}
}
if (low[s]==dfn[s]) {
scnt++;
while(!sta.empty()) {
int t=sta.top();
sta.pop();
vis[t]=;
color[t]=scnt;
if (t==s) break;
}
}
}
void solve() {
while(scanf("%d%d", &n, &m)!=EOF) {
for (int i=; i<=n; i++) {
scanf("%d", a+i);
}
init();
for (int i=; i<m; i++) {
int a, b; scanf("%d%d", &a, &b);
add(a, b);
}
for (int i=; i<=n; i++) {
if (!dfn[i]) Tarjan(i);
}
for (int u=; u<=n; u++) {
for (int i=head[u]; ~i; i=e[i].next) {
int v=e[i].v;
if (color[u]!=color[v]) {
du[color[v]]++;
}
}
}
int ans=, ansnum=;
for (int i=; i<=scnt; i++) {
if (!du[i]) {
ans++;
int num=INF;
for (int j=; j<=n; j++) {
if (color[j]==i) {
in[i]=min(a[j], in[i]);
}
}
ansnum+=in[i];
}
}
printf("%d %d\n", ans, ansnum);
}
}
int main() {
int t = ;
//freopen("in.txt", "r", stdin);
//scanf("%d", &t);
while(t--)
solve();
return ;
}