1198
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <math.h> #include <limits.h> #include <hash_map> using namespace std; // Datatypes typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef long long ll; typedef long double ld; // Define #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define FOR(_i,_n) for(int (_i) = 0; (_i) < (_n); (_i)++) #define mp make_pair // Constants const double eps = 1e-8; const double PI = 3.1415926535897932384626433832795; #define INPUT_FILE "xo.in" #define OUTPUT_FILE "xo.out" vector< vector<int> > g; vector< vector<int> > gt; vector< set<int> > gc; vector< int > color; vector< int > vlist; vector< int > indegree; int num = 0; void transp() { for(int i = 0; i < sz(g); i++) { for(int j = 0; j < sz(g[i]); j++) { gt[g[i][j]].pb(i); } } } void cond() { for(int i = 0; i < sz(g); i++) { for(int j = 0; j < sz(g[i]); j++) { if(color[i] != color[g[i][j]]) { gc[color[i]-1].insert(color[g[i][j]]-1); indegree[color[g[i][j]]-1]++; } } } } void dfs1(int v) { color[v] = 1; for(int i = 0; i < sz(g[v]); i++) { if(color[g[v][i]] == 0) dfs1(g[v][i]); } vlist[num] = v; num--; } void dfs2(int v) { color[v] = num; for(int i = 0; i < sz(gt[v]); i++) { if(color[gt[v][i]] == 0) dfs2(gt[v][i]); } } int main(void) { #ifdef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else //freopen(INPUT_FILE, "r", stdin); //freopen(OUTPUT_FILE, "w", stdout); #endif int N; cin >> N; g.resize(N); gt.resize(N); color.resize(N); vlist.resize(N); num = N-1; for(int i = 0; i < N; i++) { int t; cin >> t; while(t != 0) { g[i].pb(t-1); cin >> t; } } for(int i = 0; i < N; i++) { if(color[i] == 0) dfs1(i); } num = 0; color.erase(color.begin(), color.end()); color.resize(N); transp(); for(int i = 0; i < N; i++) { if(color[vlist[i]] == 0) { num ++; dfs2(vlist[i]); } } gc.resize(num); indegree.resize(num); cond(); int k = -1; for(int i = 0; i < sz(indegree); i++) { if(indegree[i] == 0) { if(k != -1) { cout << "0"; return 0; } k = i; } } vector< int > res; for(int i = 0; i < sz(color); i++) { if(color[i] == (k + 1)) { res.pb(i + 1); } } sort(res.begin(), res.end()); for(int i = 0; i < sz(res); i++) { cout << res[i] << " "; } cout << "0"; return 0; }
page revision: 0, last edited: 13 Sep 2007 10:57