是的,我死了QAQ
查看原帖
是的,我死了QAQ
938950
YGW6楼主2024/5/1 20:22

好消息:过样例;

坏消息:全WA.

#include<cmath>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<queue>
using namespace std;

const int N=1e5+5,inf=0x3f3f3f3f;

int n,m;
int h[N],cnt;

int f[N];

vector<int> ans[N];

int rd[N],dfncnt,tp,s[N],dfn[N],low[N];
//dfn 深度优先搜索遍历时结点 u 被搜索的次序。
/*low 在 u 的子树中能够回溯到的最早的已经在栈中的结点。
设以 u 为根的子树为 Subtree_u。
low_u 定义为以下结点的 dfn 的最小值:Subtree_u 中的结点;
从 Subtree_u 通过一条不在搜索树上的边能到达的结点。*/
int scc[N],sc;
// 结点 i 所在 SCC 的编号
int sz[N];
// 强连通 i 的大小

struct edge
{
	int u,v,w;
}e[N];

inline void add(int u,int v)
{
	e[++cnt].u=h[u];
	e[cnt].v=v;
	h[u]=cnt;
}

inline void tarjan(int u)
{
	low[u]=dfn[u]=++dfncnt;
	s[++tp]=u;
	rd[u]=1;
	for(int i=h[u];i;i=e[i].u)
	{
		int v=e[i].v;
		if(dfn[v]==0)
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(rd[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		++sc;
		ans[sc].push_back(u);
		while(s[tp]!=u)
		{
			scc[s[tp]]=sc;
			++sz[sc];
			rd[s[tp]]=0;
			ans[sc].push_back(s[tp]);
			--tp;
		}
		scc[tp]=sc;
		++sz[sc];
		rd[s[tp]]=0;
		--tp;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);
	cout<<sc<<endl;
	for(int i=1;i<=sc;++i)
		sort(ans[i].begin(),ans[i].end());
	for(int i=1;i<=n;++i)
	{
		if(f[scc[i]])
			continue;
		f[scc[i]]=1;
		for(int j=0;j<ans[scc[i]].size();++j)
			cout<<ans[scc[i]][j]<<" ";
		cout<<endl;
	}
	return 0;
}
2024/5/1 20:22
加载中...