QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#342423#999. 边双连通分量Kevin5307#WA 1ms3620kbC++201.0kb2024-03-01 11:18:472024-03-01 11:18:54

Judging History

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

  • [2024-03-01 11:18:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3620kb
  • [2024-03-01 11:18:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
int u[500500],v[500500],n,m;
vector<int> G[500500];
int dfn[500500],low[500500],tot;
set<pii> st;
vector<vector<int>> ans;
vector<int> cur;
void dfs(int u,int fa)
{
	cur.push_back(u);
	int tmp=fa;
	dfn[u]=low[u]=++tot;
	for(auto v:G[u])
		if(v!=fa)
		{
			if(dfn[v])
				low[u]=min(low[u],low[v]);
			else
			{
				dfs(v,u);
				low[u]=min(low[u],low[v]);
			}
		}
		else fa=0;
	if(low[u]==dfn[u])
	{
		vector<int> tmp;
		do
		{
			tmp.push_back(cur.back());
			cur.pop_back();
		}
		while(tmp.back()!=u);
		ans.push_back(tmp);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>u[i]>>v[i];
		G[u[i]].push_back(v[i]);
		G[v[i]].push_back(u[i]);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			dfs(i,0);
	cout<<ans.size()<<'\n';
	for(auto arr:ans)
	{
		cout<<arr.size()<<" ";
		for(auto x:arr)
			cout<<x<<" ";
		cout<<'\n';
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3620kb

input:

4 5
0 2
0 1
3 0
2 1
2 3

output:

2
4 3 0 2 1 
1 4 

result:

wrong answer Integer 4 violates the range [0, 3]