挂在第11个点
#include<bits/stdc++.h>
using namespace std;
int dfsn[1000001];//dfs序
int low[1000001];//最小dfs序
stack<int> s;//存环
int vis[1000001],use[1000001];//防重复遍历
vector<int> road[1000001];//vector存边
int color[1000001],sum=0;//记录强连通分量数目与每个点最新的强连通分量归属
int Set[1000001];//记录每个强连通分量内节点数目
int n,m;
int deep=0;
void paint(int u)
{
s.pop();
color[u]=sum;
Set[sum]++;
vis[u]=0;
low[u]=0;
}
void tanjan(int u)
{
dfsn[u]=++deep;
low[u]=deep;
vis[u]=1;
use[u]=1;
// cout<<"已遍历到"<<u<<" dfs序"<<dfsn[u]<<endl;
s.push(u);
for(int i=0;i<road[u].size();i++)
{
int v=road[u][i];
// cout<<u<<"->"<<v<<endl;
if(dfsn[v]==0)
{
tanjan(v);
low[u]=min(low[u],low[v]);
}
else
{
// cout<<u<<"i"<<endl;
if(vis[v]!=0)
{
low[u]=min(low[u],low[v]);
}
}
}
if(dfsn[u]==low[u])
{
// cout<<"此时处在"<<u<<endl;
// cout<<u<<" "<<dfsn[u]<<" "<<low[u]<<endl;
// cout<u<<endl;
// cout<<"开始处理"<<endl;
sum++;
while(s.top()!=u)
{
// cout<<s.top()<<endl;
// cout<<"I"<<endl;
paint(s.top());
}
paint(u);
// cout<<"已退栈"<<endl;
// cout<<Set[sum]<<"点数"<<endl;
}
// use[u]=0;
return ;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
road[a].push_back(b);
}
for(int i=1;i<=n;i++)
{
// deep=0;
if(use[i]==0)
{
tanjan(i);
}
}
int ans=0;
for(int i=1;i<=sum;i++)
{
// cout<<Set[i]<<endl;
if(Set[i]>1)
ans++;
}
cout<<ans;
return 0;
}
各位dalao帮帮忙。