QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#473174#906. 强连通分量Williamxzh#RE 1ms3940kbC++23974b2024-07-11 22:44:072024-07-11 22:44:07

Judging History

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

  • [2024-07-11 22:44:07]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3940kb
  • [2024-07-11 22:44:07]
  • 提交

answer

#include <bits/stdc++.h>
#define il inline
using namespace std;
const int N=1e5+5;
int n,m,dfn[N],low[N],cnt,vis[N];
int st[N],top,bel[N],idx;
vector<int> e[N],f[N];
il void adde(int x,int y){e[x].push_back(y);}
void tarjan(int x){
    int y;dfn[x]=low[x]=++cnt,vis[x]=1,st[++top]=x;
    for(int y:e[x]){
        if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
        else if(vis[y]) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        ++idx;
        do{
            y=st[top--],bel[y]=idx,f[idx].push_back(y),vis[y]=0;
        }while(y!=x);
    }
}
int x,y,z;
int main(){
    //freopen("tarjan.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){scanf("%d%d",&x,&y),++x,++y;if(x!=y) adde(x,y);}
    for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i),top=0;
    printf("%d\n",idx);
    for(int i=idx;i;--i){
        printf("%d ",f[i].size());
        for(int x:f[i]) printf("%d ",x-1);puts("");
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3940kb

input:

6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2

output:

4
1 5 
2 4 1 
1 2 
2 3 0 

result:

ok OK

Test #2:

score: -100
Runtime Error

input:

500000 500000
389812 410922
255712 339244
274009 248522
347288 199231
235313 301629
469588 84917
364188 449407
392348 436920
26220 198288
162188 468965
274222 92196
463222 408478
231663 467768
382681 38083
412497 160479
280851 268689
101149 25450
62271 9177
38892 268598
273853 250782
191939 89247
40...

output:


result: