洛谷 P2863
[USACO06JAN] The Cow Prom S
题目描述
有一个 n n n 个点, m m m 条边的有向图,请求出这个图点数大于 1 1 1 的强连通分量个数。
输入格式
第一行为两个整数 n n n 和 m m m。
第二行至 m + 1 m+1 m+1 行,每一行有两个整数 a a a 和 b b b,表示有一条从 a a a 到 b b b 的有向边。
输出格式
仅一行,表示点数大于 1 1 1 的强连通分量个数。
样例 #1
样例输入 #1
5 4 2 4 3 5 1 2 4 1
样例输出 #1
1
提示
数据规模与约定
对于全部的测试点,保证 2 ≤ n ≤ 1 0 4 2\le n \le 10^4 2≤n≤104, 2 ≤ m ≤ 5 × 1 0 4 2\le m\le 5\times 10^4 2≤m≤5×104, 1 ≤ a , b ≤ n 1 \leq a, b \leq n 1≤a,b≤n。
#include using namespace std; #define N 10005 vector G[N]; //vis 只记录当前连通分量的访问情况(即是否可达),used记录全局的 bool used[N] = {0}, vis[N] ={0}; int indexx = 0,dfn[N] = {0},low[N] = {0},color[N] = {0}; int colornum = 0; stack s; void paint() { int now = s.top(); s.pop(); color[colornum]++; //这里释放点的访问情况(是否在栈中/是否是当前的联通中) //记录一个点是否在栈中是为了正确判断节点之间的可达性,进而确定哪些节点构成了强连通分量。 vis[now] = false; } void dfs(int now) { if(vis[now] == true) return ; vis[now] = true; used[now] = true; s.push(now); low[now] = dfn[now] = ++indexx; for(int i=0;i int child = G[now][i]; //如果已经记录时间戳但没有访问的节点不会进入栈中 if(dfn[child] == 0) { dfs(child); low[now] = min(low[now],low[child]); }//没有分配时间戳则说明未被先前的联通量所搜索 //分配了时间戳也要检测是否可达(在栈中) else if(vis[child])//else分支一定要加,否则一定会进入 { low[now] = min(low[now],dfn[child]); } } if(low[now] == dfn[now]) { colornum++; while(s.top()!=now) { paint(); } paint(); } } int main() { int n,m; cin>n>>m; for(int i=0;i int from,to; cin>from>>to; G[from].push_back(to); } for(int i = 1;i if(used[i] == false) dfs(i); } int ans = 0; for(int i = 1;i if(color[i]1) ans++; } cout