QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#92760 | #906. 强连通分量 | fzj2007# | WA | 8ms | 22296kb | C++14 | 1.9kb | 2023-03-30 21:37:23 | 2023-03-30 21:37:26 |
Judging History
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)