QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#792595#999. 边双连通分量RDFZchenyyWA 2ms9644kbC++141015b2024-11-29 11:46:552024-11-29 11:46:55

Judging History

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

  • [2024-11-29 11:46:55]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9644kb
  • [2024-11-29 11:46:55]
  • 提交

answer

#include<bits/stdc++.h>

#define MAXN 200005

int n,m,x,y;
std::vector<int> g[MAXN];
int dfn[MAXN],low[MAXN],idx;
int st[MAXN],tp;
std::vector<std::vector<int>> ans;

void tarjan(int u,int fa){
//	std::cout<<"TARJAN"<<' '<<u<<' '<<fa<<'\n';
	dfn[u]=low[u]=++idx;
	st[++tp]=u;
	for(int v:g[u]){
		if(v==fa) continue;
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=std::min(low[u],low[v]);
		}else low[u]=std::min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		std::vector<int> now;
		while(st[tp]!=u){
			now.push_back(st[tp--]); 
		}
		now.push_back(st[tp--]);
		ans.push_back(now);
	}
	
	return;
}

int main(){
	std::ios::sync_with_stdio(false);
	
	std::cin>>n>>m;
	for(int i=1;i<=m;i++){
		std::cin>>x>>y;
		g[x].push_back(y),g[y].push_back(x);
	}
	for(int i=0;i<=n-1;i++){
		if(!dfn[i]) tarjan(i,0);
	}
	std::cout<<ans.size()<<'\n';
	for(std::vector<int> nvec:ans){
		std::cout<<nvec.size()<<' ';
		for(int j:nvec) std::cout<<j<<' ';
		std::cout<<'\n'; 
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9260kb

input:

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

output:

1
4 3 1 2 0 

result:

ok OK

Test #2:

score: 0
Accepted
time: 2ms
memory: 9644kb

input:

13 21
4 5
8 7
12 3
3 10
1 5
10 2
0 0
11 4
2 12
9 1
9 0
7 8
7 6
9 1
8 2
12 10
11 0
8 6
3 2
5 9
4 11

output:

3
6 11 4 5 1 9 0 
3 6 7 8 
4 12 3 10 2 

result:

ok OK

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 8540kb

input:

2 2
0 1
1 0

output:

2
1 1 
1 0 

result:

wrong answer # of tecc is differ - expected: '1', found: '2'