QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#480224 | #906. 强连通分量 | Hanghang# | WA | 2ms | 9276kb | C++14 | 752b | 2024-07-16 10:40:54 | 2024-07-16 10:40:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int N=1e5+3;
int n,m,tim,tot,top,dfn[N],low[N],col[N],sta[N];
vector<int>ve[N],ans[N];
void Dfs(int x)
{
low[x]=dfn[x]=++tim;sta[++top]=x;
for(int y:ve[x])
{
if(dfn[y]){if(!col[y])low[x]=min(low[x],dfn[y]);continue;}
Dfs(y);low[x]=min(low[x],low[y]);
}
if(dfn[x]==low[x])for(tot++;sta[top+1]!=x;top--)col[sta[top]]=tot;
}
int main()
{
cin>>n>>m;
for(int i=1,x,y;i<=m;i++)
cin>>x>>y,ve[++x].push_back(++y);
for(int i=1;i<=n;i++)if(!dfn[i])Dfs(i);
cout<<tot<<endl;
for(int i=1;i<=n;i++)ans[col[i]].pb(i);
for(int i=1;i<=tot;i++,cout<<endl)
{
cout<<ans[i].size()<<" ";
for(int x:ans[i])cout<<x-1<<" ";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 9276kb
input:
6 7 1 4 5 2 3 0 5 5 4 1 0 3 4 2
output:
4 2 0 3 1 2 2 1 4 1 5
result:
wrong answer 5 is later than 2, but there is an edge (5, 2)