#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<bitset> #include<set> #include<map> #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define FORD(i,a,b) for(int i=(a);i>=(b);i--) #define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++) #define all(c) (c).begin(),(c).end() #define scanf(...) scanf(__VA_ARGS__)?:0 #define eprintf(...) fprintf(stderr,__VA_ARGS__),fflush(stderr) #define e1 first #define e2 second #define mp make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ll,int> pli; typedef pair<int,ll> pil; int n,m,x,a,b,k,kt,ilew1,skl[500001],ile[500001],ciag[500001],pos[500001],tree[500001],tree2[500001]; vector<int> v[500001],vr[500001],w; bitset<500001> odw; stack<int,vector<int> >stos; void add(int *tree,int a,int b) { a--; while (b) tree[b]++,b-=b&-b; while (a) tree[a]--,a-=a&-a; } int query(int *tree,int a) { int ret=0; while (a<=ile[kt]) ret+=tree[a],a+=a&-a; return ret; } void dfswrzuc(int a) { odw[a]=true; foreach(it,v[a]) if (!odw[*it]) dfswrzuc(*it); stos.push(a); } void dfspodziel(int a) { odw[a]=true; skl[a]=k; ile[k]++; foreach(it,vr[a]) if (!odw[*it]) dfspodziel(*it); } void dfssort(int a) { odw[a]=true; foreach(it,v[a]) if (!odw[*it] && skl[*it]==kt) dfssort(*it); ciag[++x]=a; pos[a]=x; } int main() { scanf("%d%d",&n,&m); REP(i,m) scanf("%d%d",&a,&b),v[a].pb(b),vr[b].pb(a); FOR(i,1,n) if (!odw[i]) dfswrzuc(i); odw.reset(); while (!stos.empty()) { if (!odw[stos.top()]) k=stos.top(),dfspodziel(stos.top()); stos.pop(); } FOR(i,1,n) if (ile[i]>1) ilew1++,kt=i; if (!ilew1) puts("NIE"),exit(0); if (ilew1>1) puts("0\n"),exit(0); odw.reset(); FOR(i,1,n) if (skl[i]==kt && !odw[i]) dfssort(i); assert(x==ile[kt]); reverse(ciag+1,ciag+ile[kt]+1); FOR(i,1,n) pos[i]=ile[kt]-pos[i]+1; FOR(i,1,n) if (skl[i]==kt) foreach(it,v[i]) if (skl[*it]==kt) { if (pos[*it]>pos[i]) add(tree,pos[i]+1,pos[*it]-1); else add(tree2,1,pos[*it]-1),add(tree2,pos[i]+1,ile[kt]); } FOR(i,1,ile[kt]) if (!(query(tree,i)|query(tree2,i))) w.pb(ciag[i]); printf("%lu\n",w.size()); sort(all(w)); foreach(it,w) printf("%d ",*it); puts(""); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 | #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<bitset> #include<set> #include<map> #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define FORD(i,a,b) for(int i=(a);i>=(b);i--) #define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++) #define all(c) (c).begin(),(c).end() #define scanf(...) scanf(__VA_ARGS__)?:0 #define eprintf(...) fprintf(stderr,__VA_ARGS__),fflush(stderr) #define e1 first #define e2 second #define mp make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int uint; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ll,int> pli; typedef pair<int,ll> pil; int n,m,x,a,b,k,kt,ilew1,skl[500001],ile[500001],ciag[500001],pos[500001],tree[500001],tree2[500001]; vector<int> v[500001],vr[500001],w; bitset<500001> odw; stack<int,vector<int> >stos; void add(int *tree,int a,int b) { a--; while (b) tree[b]++,b-=b&-b; while (a) tree[a]--,a-=a&-a; } int query(int *tree,int a) { int ret=0; while (a<=ile[kt]) ret+=tree[a],a+=a&-a; return ret; } void dfswrzuc(int a) { odw[a]=true; foreach(it,v[a]) if (!odw[*it]) dfswrzuc(*it); stos.push(a); } void dfspodziel(int a) { odw[a]=true; skl[a]=k; ile[k]++; foreach(it,vr[a]) if (!odw[*it]) dfspodziel(*it); } void dfssort(int a) { odw[a]=true; foreach(it,v[a]) if (!odw[*it] && skl[*it]==kt) dfssort(*it); ciag[++x]=a; pos[a]=x; } int main() { scanf("%d%d",&n,&m); REP(i,m) scanf("%d%d",&a,&b),v[a].pb(b),vr[b].pb(a); FOR(i,1,n) if (!odw[i]) dfswrzuc(i); odw.reset(); while (!stos.empty()) { if (!odw[stos.top()]) k=stos.top(),dfspodziel(stos.top()); stos.pop(); } FOR(i,1,n) if (ile[i]>1) ilew1++,kt=i; if (!ilew1) puts("NIE"),exit(0); if (ilew1>1) puts("0\n"),exit(0); odw.reset(); FOR(i,1,n) if (skl[i]==kt && !odw[i]) dfssort(i); assert(x==ile[kt]); reverse(ciag+1,ciag+ile[kt]+1); FOR(i,1,n) pos[i]=ile[kt]-pos[i]+1; FOR(i,1,n) if (skl[i]==kt) foreach(it,v[i]) if (skl[*it]==kt) { if (pos[*it]>pos[i]) add(tree,pos[i]+1,pos[*it]-1); else add(tree2,1,pos[*it]-1),add(tree2,pos[i]+1,ile[kt]); } FOR(i,1,ile[kt]) if (!(query(tree,i)|query(tree2,i))) w.pb(ciag[i]); printf("%lu\n",w.size()); sort(all(w)); foreach(it,w) printf("%d ",*it); puts(""); } |