QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#481140#906. 强连通分量xyloph0nex17#WA 0ms18000kbC++141.5kb2024-07-16 20:46:362024-07-16 20:46:36

Judging History

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

  • [2024-07-16 20:46:36]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:18000kb
  • [2024-07-16 20:46:36]
  • 提交

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)