noip前两天开始学这玩意…………
强连通(模版 元问题byscy)
模板题,我感觉不难。
另外可以用来缩点,在开一个邻接表,不再在一个强联通分量的连边就好。
#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std; const int MAXN = 2e4 + 10; const int MAXM = 2e5 + 10; struct Edge{ int to, next; } e[MAXM]; int head[MAXN], tot, n, m; int low[MAXN], dfn[MAXN], id; int belong[MAXN], ins[MAXN], cnt; int sta[MAXN], top; void AddEdge(int from, int to) { e[tot] = Edge{to, head[from]}; head[from] = tot++; } void tarjan(int u) { low[u] = dfn[u] = ++id; sta[++top] = u; ins[u] = 1; for(int i = head[u]; ~i; i = e[i].next) { int v = e[i].to; if(!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if(ins[v]) low[u] = min(low[u], low[v]); } if(dfn[u] == low[u]) { ++cnt; while(1) { int v = sta[top--]; ins[v] = 0; belong[v] = cnt; if(u == v) break; } } } int main() { memset(head, -1, sizeof(head)); tot = 0; scanf("%d%d", &n, &m); _for(i, 1, m) { int u, v; scanf("%d%d", &u, &v); AddEdge(u, v); } _for(i, 1, n) if(!dfn[i]) tarjan(i); printf("%d\n", cnt); return 0; }