只A#6求调
查看原帖
只A#6求调
688956
daitangchen2008楼主2024/7/5 15:32
#include <bits/stdc++.h>
using namespace std;
int n,m,cnt,ans;
vector<int> edge[10010];
priority_queue<int,vector<int>,greater<>>p[10010];
bool instack[10010];
int dfn[10010];
int low[10010];
int scc[10010];
stack<int> s;
void Tarjan(int u)
{
	++cnt;
	dfn[u]=low[u]=cnt;
	s.push(u);
	instack[u]=true;
	for(int v:edge[u])
	{
		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])
	{
		ans++;
		int temp;
		do
		{
			temp=s.top();
			s.pop();
			instack[temp]=false;
			scc[temp]=ans;
			p[ans].push(temp);
		}while(temp!=u);
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			Tarjan(i);
	cout<<ans<<endl;
	for(int i=1;i<=n;i++)
	{
		if(!p[scc[i]].empty())
		{
			while (!p[scc[i]].empty()) {
				cout << p[scc[i]].top() << " ";
				p[scc[i]].pop();
			}
			cout << endl;
		}
	}
	return 0;
}
2024/7/5 15:32
加载中...