QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#343035#906. 强连通分量ycz#WA 23ms191120kbC++141.1kb2024-03-01 21:13:482024-03-01 21:13:50

Judging History

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

  • [2024-03-01 21:13:50]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:191120kb
  • [2024-03-01 21:13:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define fq(i,l,r) for(int i=(l);i<=(r);i++)
#define ffq(i,r,l) for(int i=(r);i>=(l);i--)
#define ftq(i,l,r,t) for(int i=(l);i<=(r);i+=(t))
#define pii pair<int,int>
#define F first
#define S second 
#define cintree fq(i,1,n-1){int u,v;cin>>u>>v,q[u].push_back(v),q[v].push_back(u);}
const int inf=1e9+7,N=4e6+9;
int n,m,u,v,dfn[N],low[N],cnt,b[N],vis[N];
vector<pii> q[N];
vector<int> c[N];
void tarjan(int p,int wh){
    dfn[p]=low[p]=++cnt;
    for(auto u:q[p]) 
        if(!dfn[u.F]) tarjan(u.F,u.S),low[p]=min(low[p],low[u.F]);
        else if(u.S!=wh) low[p]=min(low[p],dfn[u.F]);
    if(dfn[p]==low[p]) b[wh]=1;
}
void dfs(int p,int t){
    c[t].push_back(p),vis[p]=1;
    for(auto u:q[p]) if(!b[u.S]&&!vis[u.F]) dfs(u.F,t);
}
int main(){
    cin>>n>>m;
    fq(i,1,m) cin>>u>>v,u++,v++,q[u].push_back({v,i});
    fq(i,1,n) if(!dfn[i]) tarjan(i,0);cnt=0;
    fq(i,1,n) if(!vis[i]) dfs(i,++cnt);
    cout<<cnt<<endl;
    fq(i,1,cnt){cout<<c[i].size()<<" ";for(auto u:c[i]) cout<<u-1<<" ";cout<<endl;}
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 23ms
memory: 191120kb

input:

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

output:

4
2 0 3 
2 1 4 
1 2 
1 5 

result:

wrong answer 5 is later than 2, but there is an edge (5, 2)