tarjan
算法思想
模板
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define cin(a) scanf("%d",&a)
#define pii pair<int,int>
#define ll long long
#define gcd __gcd
const int inf = 0x3f3f3f3f;
const int maxn = 10100;
const int M = 1e9+7;
int n,m,idx,top,cnt;
int dfn[maxn]; //这个点是第几个被访问的
int low[maxn]; //这个点所能到的点的dfn的最小值
bool vis[maxn]; //是否在s中
int s[maxn]; //栈
vector<int> a[maxn]; //图
void tarjan(int u)
{
dfn[u] = low[u] = ++idx;
s[++top] = u;
vis[u] = 1;
for(auto v : a[u])
{
if(!dfn[v]) //如果这个点还没被访问过
{
tarjan(v);
low[u] = min(low[u],low[v]); //回溯
}
else if(vis[v]) //如果这个点在栈内
{
low[u] = min(low[u],low[v]);
}
}
if(dfn[u] == low[u]) //找到一组强连通分量
{
if(s[top] != u) cnt++;
while (s[top] != u)
{
vis[s[top]] = 0;
top--;
}
vis[s[top]] = 0;
top--;
}
}
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("data.in", "r", stdin);
//freopen("data.out", "w", stdout);
#endif
cin(n),cin(m);
for(int i = 0,u,v; i < m; i++)
{
scanf("%d%d",&u,&v);
a[u].push_back(v);
}
for(int i = 1; i <= n; i++)
{
if(dfn[i] == 0)
{
tarjan(i);
}
}
cout<<cnt<<endl;
return 0;
}
例题
https://www.luogu.com.cn/problem/P2863