QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#792595 | #999. 边双连通分量 | RDFZchenyy | WA | 2ms | 9644kb | C++14 | 1015b | 2024-11-29 11:46:55 | 2024-11-29 11:46:55 |
Judging History
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'