QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#92760#906. 强连通分量fzj2007#WA 8ms22296kbC++141.9kb2023-03-30 21:37:232023-03-30 21:37:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-30 21:37:26]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:22296kb
  • [2023-03-30 21:37:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace IO{
	template<typename T>inline bool read(T &x){
		x=0;
		char ch=getchar();
		bool flag=0,ret=0;
		while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
		while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
		x=flag?-x:x;
        return ret;
	}
	template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
	    return read(a)&&read(args...);
	}
	template<typename T>void prt(T x){
		if(x>9) prt(x/10);
		putchar(x%10+'0');
	}
	template<typename T>inline void put(T x){
		if(x<0) putchar('-'),x=-x;
		prt(x);
	}
	template<typename T>inline void put(char ch,T x){
		if(x<0) putchar('-'),x=-x;
		prt(x);
		putchar(ch);
	}
	template<typename T,typename ...Args>inline void put(T a,Args ...args){
	    put(a);
		put(args...);
	}
	template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
	    put(ch,a);
		put(ch,args...);
	}
	inline void put(string s){
		for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
	}
	inline void put(const char* s){
		for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
	}
}
using namespace IO;
#define N 500005
int n,m;
struct edge{
	int v,nxt;
}e[N<<1];
int st[N],tp,dfn[N],low[N],vis[N],idx,cnt,head[N],ans;
inline void add(int u,int v){
	e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}
vector<int> g[N];
inline void tarjan(int x){
	st[++tp]=x,dfn[x]=low[x]=++idx,vis[x]=1;
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		if(!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);
		else if(vis[v]) low[x]=min(low[x],dfn[v]);
	}
	if(dfn[x]==low[x]){
		int v;ans++;
		do v=st[tp--],g[ans].emplace_back(v),vis[v]=0;
		while(v!=x);
	}
}
int main(){
	read(n,m);
	for(int i=1,u,v;i<=m;i++) read(u,v),add(u+1,v+1);
	for(int i=1;i<=n;i++) 
		if(!dfn[i]) tp=0,tarjan(i);
	put('\n',ans);
	for(int i=1;i<=ans;i++){
		put(' ',g[i].size());
		for(auto v:g[i]) put(' ',v-1);
		putchar('\n');
	}
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 22296kb

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)