QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#482099#906. 强连通分量DoqeWA 0ms53600kbC++14777b2024-07-17 17:15:102024-07-17 17:15:10

Judging History

你现在查看的是最新测评结果

  • [2024-07-17 17:15:10]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:53600kb
  • [2024-07-17 17:15:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int>scc[N],to[N];
int dfn[N],low[N],tt,in[N],cnt;
int sta[N],top;
void tarjan(int u)
{
	sta[++top]=u,in[u]=1;
	dfn[u]=++tt,low[u]=tt;
	for(int v:to[u])
		if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
		else if(in[v])low[u]=min(low[u],dfn[v]);
	if(dfn[u]==low[u])
	{
		int k;++cnt;
		do
		{
			k=sta[top--];in[k]=0;
			scc[cnt].push_back(k);
		}while(k!=u);
	}
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		int u,v;cin>>u>>v;
		to[u].push_back(v);
	}
	for(int i=0;i<n;++i)
		if(!dfn[i])tarjan(i);
	cout<<cnt<<"\n";
	for(int i=1;i<=cnt;++i)
	{
		cout<<scc[i].size();
		for(int j:scc[i])cout<<" "<<j;cout<<"\n";
	}
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 53600kb

input:

6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2

output:

4
2 3 0
1 2
2 4 1
1 5

result:

wrong answer 5 is later than 2, but there is an edge (5, 2)