QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#481140 | #906. 强连通分量 | xyloph0nex17# | WA | 0ms | 18000kb | C++14 | 1.5kb | 2024-07-16 20:46:36 | 2024-07-16 20:46:36 |
Judging History
answer
//El Psy Kongroo
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ri int
#define TIME (1e3 * clock() / CLOCKS_PER_SEC)
using namespace std ;
template <typename T>
inline void read(T&x){
x = 0 ; char c = getchar() ; bool flg = 1 ; while(c > '9' || c < '0'){if(c == '-')flg = 0 ; c = getchar() ;}
while(c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48) ; c = getchar() ;} x = flg ? x : -x ;
}
template <typename T,typename ...Args>
inline void read(T&x,Args&...args){read(x),read(args...);}
bool m_bg ;
const int N = 5e5 + 10 ;
struct star{int to,pre ;}e[N*2] ; int head[N<<1],strn=1 ;
struct line{int u,v ;}L[N] ;
void add(int u,int v){e[++strn].to=v,e[strn].pre=head[u],head[u]=strn ;}
int dfn[N],low[N],dfnn,sc[N],scn,stk[N],top ; vector<int>scc[N] ;
void tarjan(int u){
dfn[u] = low[u] = ++dfnn ; stk[++top] = u ;
for(ri i = head[u] , v ; i ; i = e[i].pre){
v=e[i].to ;
if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]) ;
else if(!sc[v])low[u]=min(low[u],dfn[v]) ;
}
if(dfn[u]==low[u]){
sc[u]=++scn ;
while(top&&stk[top]!=u)scc[scn].pb(stk[top]),sc[stk[top]]=scn,top-- ;
scc[scn].pb(u),top-- ;
}
}
int n,m ;
bool m_ed ;
signed main(){
//freopen("a.in","r",stdin) ;
read(n,m) ; for(ri i = 1 , u , v ; i <= m ; i++)read(u,v),u++,v++,add(u,v) ;
for(ri i = 1 ; i <= n ; i++)if(!dfn[i])tarjan(i) ;
printf("%d\n",scn) ;
for(ri i = 1 ; i <= scn ; i++){
printf("%d ",(int)scc[i].size()) ;
for(ri j : scc[i])printf("%d ",j-1) ; putchar('\n') ;
}
return 0 ;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 18000kb
input:
6 7 1 4 5 2 3 0 5 5 4 1 0 3 4 2
output:
4 2 3 0 1 2 2 4 1 1 5
result:
wrong answer 5 is later than 2, but there is an edge (5, 2)