526互联

图论强联通分量（tarjan）算法

发布时间 2023-08-04 15:53:21作者: 黄浠锐

图论强联通分量（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;
}