[USACO06JAN] The Cow Prom S

题目描述

有一个 $n$ 个点，$m$ 条边的有向图，请求出这个图点数大于 $1$ 的强连通分量个数。

输入格式

第一行为两个整数 $n$ 和 $m$。

第二行至 $m+1$ 行，每一行有两个整数 $a$ 和 $b$，表示有一条从 $a$ 到 $b$ 的有向边。

输出格式

仅一行，表示点数大于 $1$ 的强连通分量个数。

样例 #1

样例输入 #1

5 4
2 4
3 5
1 2
4 1

样例输出 #1

1

提示

数据规模与约定

对于全部的测试点，保证 $2\le n\le 10^4$，$2\le m\le 5\times 10^4$，$1\le a,b\le n$。

#include <bits/stdc++.h>
using namespace std;
#define N 10005
vector<int> 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<int> 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<G[now].size();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<m;i++){int from,to;cin>>from>>to;G[from].push_back(to);}	for(int i = 1;i<=n;i++){if(used[i] == false) dfs(i);}int ans = 0;for(int i = 1;i<=colornum;i++){if(color[i]>1) ans++;}cout<<ans;return 0;}