QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#342423 | #999. 边双连通分量 | Kevin5307# | WA | 1ms | 3620kb | C++20 | 1.0kb | 2024-03-01 11:18:47 | 2024-03-01 11:18:54 |
Judging History
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]