Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <bitset>
- #include <deque>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <iostream>
- #include <list>
- #include <map>
- #include <queue>
- #include <set>
- #include <sstream>
- #include <stack>
- #include <string>
- #include <utility>
- #include <iomanip>
- #include <vector>
- #define fst first
- #define snd second
- #define all(x) (x).begin(), (x).end()
- #define clr(a, v) memset( a , v , sizeof(a) )
- #define pb push_back
- #define mp make_pair
- #define sz size()
- #define FORN( i , s , n ) for( int i = (s) ; i < (n) ; i++ )
- #define FOR( i , n ) FORN( i , 0 , n )
- #define FORIT( i , x ) for( typeof x.begin() i = x.begin() ; i != x.end() ; i++ )
- #define trace(x) cerr << #x << ": " << x << endl;
- #define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
- #define read ios::sync_with_stdio(false)
- using namespace std;
- typedef long long int64;
- typedef vector <int> vi;
- typedef pair <int,int> ii;
- typedef vector <string> vs;
- typedef vector <ii> vii;
- vi adj [2005];
- int vis [2005];
- int num [2005];
- int low [2005];
- int comp[2005];
- int indegree [2005];
- int S[2005];
- int ts;
- int contn, compcont;
- void dfs(int v){
- num[v] = low[v] = contn++;
- vis[v] = 1;
- S[ts++] = v;
- FOR(i,adj[v].sz){
- int u = adj[v][i];
- if ( num[u] == -1 ) dfs(u);
- if ( vis[u] ) low[v] = min(low[v],low[u]);
- }
- if ( low[v] == num[v] ){
- while(1){
- int u = S[ts-1]; ts--;
- comp[u] = compcont;
- vis[u] = 0;
- if ( u==v ) break;
- }
- compcont++;
- }
- }
- int main(){
- read;
- int N,v;
- cin>>N;
- FOR(i,N)
- while(cin>>v and v)
- adj[i].pb(v-1);
- contn = compcont = 0;
- FOR(i,N) {vis[i]=0; num[i]=-1;}
- ts = 0;
- FOR(i,N) if (num[i]==-1) dfs(i);
- FOR(i,compcont) indegree[i]=0;
- FOR(i,N)
- FOR(j,adj[i].sz) if ( comp[i]!=comp[adj[i][j]] ) indegree[comp[adj[i][j]]]++;
- int one = 0, SCC =-1;
- FOR(i,compcont) if ( indegree[i]==0 ) {one++;SCC=i;}
- if(one==1)
- FOR(i,N) if ( comp[i]==SCC ) cout<<i+1<<" ";
- cout<<0<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement