QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#343035 | #906. 强连通分量 | ycz# | WA | 23ms | 191120kb | C++14 | 1.1kb | 2024-03-01 21:13:48 | 2024-03-01 21:13:50 |
Judging History
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;
}
詳細信息
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)