QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#44617 | #906. 强连通分量 | CCPSDCGK# | WA | 9ms | 28816kb | C++23 | 2.3kb | 2022-08-20 12:57:50 | 2022-08-20 12:57:51 |
Judging History
answer
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<cmath>
#include<ctime>
#include<bitset>
#include<vector>
#include<cstdio>
#include<string>
#include<random>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
using ll=long long;
using uint=unsigned int;
using ull=unsigned long long;
#define endl '\n'
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define fs fflush(stdout)
#define ump unordered_map
#define pq priority_queue
#define clz __builtin_clz
#define ctz __builtin_ctz
#define sz(x) (int)x.size()
#define np next_permutation
#define clzl __builtin_clzll
#define ctzl __builtin_ctzll
#define ppc __builtin_popcount
#define all(x) x.begin(),x.end()
#define ppcl __builtin_popcountll
#define fpi(x) freopen(x,"r",stdin)
#define fpo(x) freopen(x,"w",stdout)
#define uid uniform_int_distribution
#define urd uniform_real_distribution
#define me(x,y) memset(x,y,sizeof(x))
#define dbg(x) cerr<<"In Line "<<__LINE__<<' '<<#x<<'='<<(x)<<'\n'
#define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,iosiz,stdin),p1==p2)?EOF:*p1++
#define iosiz 1024
char buf[iosiz],*p1=buf,*p2=buf;
template<class T> inline T &re(T &x){
x=0;int f=1;char ch=gc;
while(ch<48||ch>57){
if(ch==45) f=-f;ch=gc;
}
while(ch>47&&ch<58) x=(x<<1)+(x<<3)+(ch^48),ch=gc;
return x*=f;
}
#define mod 998244353
#define inf 0x3f3f3f3f
int cnt,dfn[500005],tim,low[500005],s[500005],scc[500005],top;
bool is[500005];
vector<int> v[500005],edge[500005];
void dfs(int u){
dfn[u]=low[u]=++tim,is[s[++top]=u]=1;
for(int v:edge[u]){
if(!dfn[v]) dfs(v),low[u]=min(low[u],low[v]);
else if(is[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
cnt++;
do{
scc[s[top]]=cnt,is[s[top]]=0;
}while(s[top--]^u);
}
}
int main(){
#ifdef CCPSDCGK
fpi("shuju.txt");
#endif
int n=re(n),m=re(m);
while(m--){
int u=re(u),v=re(v);
edge[u].eb(v);
}
for(int i=0;i<n;i++) if(!dfn[i]) dfs(i);
for(int i=0;i<n;i++) v[scc[i]].eb(i);
cout<<cnt<<endl;
for(int i=1;i<=cnt;i++){
cout<<sz(v[i])<<' ';
for(int pos:v[i]) cout<<pos<<' ';cout<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 9ms
memory: 28816kb
input:
6 7 1 4 5 2 3 0 5 5 4 1 0 3 4 2
output:
4 2 0 3 1 2 2 1 4 1 5
result:
wrong answer 5 is later than 2, but there is an edge (5, 2)