kasaruju求调
  • 板块灌水区
  • 楼主GODTREE
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/3/24 11:42
  • 上次更新2024/3/24 13:50:58
查看原帖
kasaruju求调
776799
GODTREE楼主2024/3/24 11:42

re了

#include <bits/stdc++.h>
#define N 50005
using namespace std;
struct edge
{
	int nxt,to;
}e[N],fe[N];
int n,m,head[N],cnt,s[N],fcnt,od[N],fhead[N];
vector<int> scc[N];
bool vis[N];
void add(int u,int v)
{
	e[++cnt].nxt=head[u];
	head[u]=cnt;
	e[cnt].to=v;
}
void fadd(int u,int v)
{
	fe[++fcnt].nxt=fhead[u];
	fhead[u]=fcnt;
	fe[fcnt].to=v;
}
void dfs1(int u)
{
	vis[u]=1;
	for (int i=head[u];i!=0;i=e[i].nxt)
	{
		int v=e[i].to;
		if(vis[v]==0)
		{
			dfs1(v);
		}
	}
	s[++cnt]=u;
}
void dfs2(int u)
{
	vis[u]=1;
	for (int i=fhead[u];i!=0;i=fe[i].nxt)
	{
		int v=fe[i].to;
		if(vis[v]==0)
		{
			dfs2(v);
		}
	}
	scc[cnt].push_back(u);
}
int main()
{
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		fadd(y,x);
	}
	cnt=0;
	dfs1(1);
	memset(vis,0,sizeof(vis));
	cnt=0;
	for (int i=n;i>=1;i--)
	{
		if (vis[s[i]]==0)
		{
			dfs2(s[i]);
			od[s[i]]=cnt;
		}
		cnt++;
	}
	for (int i=1;i<=n;i++)
	{
		sort(scc[i].begin(),scc[i].end());
	}
	for (int i=1;i<=n;i++)
	{
		if(vis[i]==0)
		{
			for (int j=0;j<scc[i].size();j++)
			{
				cout<<scc[i][j]<<" ";
			}
		}
		cout<<"\n";
	}
	return 0;
}
2024/3/24 11:42
加载中...