寒鸽儿のBlog

到现在才来学强连通分量QaQ

注意理解非树边对low的更新:
只有返祖边入点的dfn和入点未划到强连通分量里的横叉边才是合理的更新low。其他非树边均不可。然后根据dfs的性质,应当判断非树边指向的点有没有加入强连通分量。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 12345, M = 56789;
int head[N], ver[M], nex[M], my[M], tot;
inline void addedge(int u, int v) {
	ver[tot] = v; nex[tot] = head[u]; my[tot] = u; head[u] = tot++;
}

int dfn[N], low[N], cl[N], sta[N], outd[N], num[N], top = 0, dfs_clock = 1, col = 1;
void dfs(int cur) {
	dfn[cur] = low[cur] = dfs_clock++;
	sta[top++] = cur;
	for(int i = head[cur]; ~i; i = nex[i]) {
		if(!dfn[ver[i]]) {
			dfs(ver[i]);
			low[cur] = min(low[cur], low[ver[i]]);
		} else if(!cl[ver[i]]) {
			low[cur] = min(low[cur], dfn[ver[i]]);
		}
	}
	if(dfn[cur] == low[cur]) {
		--top;
		while(sta[top] != cur) {
			cl[sta[top]] = col;
			++num[col];
			--top;
		}
		cl[cur] = col;
		++num[col];
		++col;
	}
}

int main() {
	memset(head, -1, sizeof(head));
	int n, m, u, v, tms = 0, ans;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d %d", &u, &v);
		addedge(u, v);
	}
	for(int i = 1; i <= n; ++i) if(!dfn[i]) 
		dfs(i);
	for(int i = 0; i < tot; ++i) {
		if(cl[my[i]] != cl[ver[i]]) {
			++outd[cl[my[i]]];
		}
	}
	for(int i = 1; i < col; ++i)
		if(!outd[i]) {
			++tms;
			ans = num[i];
		}
	if(tms == 1) {
		printf("%d\n", ans);
	} else {
		printf("0\n");
	}
	return 0;	
}