图论强联通分量（tarjan）算法
图论强联通分量（tarjan）算法
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,cntb,ans;
vector<int> edge[101];
vector<int> belong[101];
bool instack[101];
int dfn[101];
int low[101];
stack<int> s;
void Tarjan(int u)
{
++cnt;
dfn[u]=low[u]=cnt;
s.push(u);
instack[u]=true;
for(int i=0;i<edge[u].size();++i)
{
int v=edge[u][i];
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
++cntb;
int node;
do
{
node=s.top();
s.pop();
instack[node]=false;
belong[cntb].push_back(node);
}while(node!=u);
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;++i)
{
int u,v;
cin>>u>>v;
edge[u].push_back(v);
}
Tarjan(1);
for(int i=1;i<=cntb;++i)
{
for(int j=0;j<belong[i].size();++j)
ans++;
}
cout<<ans;
return 0;
}