QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#479873 | #906. 强连通分量 | liuhangxin# | WA | 0ms | 16052kb | C++14 | 1.3kb | 2024-07-15 21:27:45 | 2024-07-15 21:27:45 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=5e5+10;
int n,m;
vector<pii>to[N];
int dfn[N],low[N],tot;
int stk[N],cnt;
bool vis[N],instk[N];
vector<vector<int>>tmp;
inline void dfs(int u,int fa)
{
dfn[u]=low[u]=++tot;
stk[++cnt]=u;instk[u]=1;
for(pii t:to[u]){
int v=t.fi;
if(t.se==fa)continue;
if(!dfn[v])
{
dfs(v,t.se);
low[u]=min(low[u],low[v]);
}
else if(instk[v])low[u]=min(low[u],dfn[v]);
}
// cout<<u<<" "<<dfn[u]<<" "<<low[u]<<endl;
if(dfn[u]==low[u])
{
int x;
vector<int>res;
do
{
x=stk[cnt--];
res.push_back(x);
instk[x]=0;
}while(x!=u);
tmp.push_back(res);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
to[a].push_back({b,i});
to[b].push_back({a,i});
}
for(int i=0;i<n;i++)
if(!dfn[i])
dfs(i,0);
printf("%d\n",(int)tmp.size());
for(vector<int>res:tmp)
{
printf("%d ",(int)res.size());
for(int x:res)printf("%d ",x);
puts("");
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 16052kb
input:
6 7 1 4 5 2 3 0 5 5 4 1 0 3 4 2
output:
4 2 3 0 1 5 1 2 2 4 1
result:
wrong answer 4 is later than 2, but there is an edge (4, 2)