【暑训排位 #5 D】 Jobbery tarjan 缩点

Hard times came for Martian senate. Even this pride of Martian democracy can not oppose the almighty jobbery. Let’s consider the procedure of typical decision making. A member of Martian senate, who needs a certain law, submits it to senate. To improve his chances that law is accepted, he makes a phone call to each of senate members on whom he has the goods in his safe. Then he kindly suggests to those senators to support the new law. Moreover, to avoid occasional rejection of this important law, he asks each of them to make the same procedure with their safes. And each of them having no choice makes a similar range of phone calls to those on whome, in turn, he has the goods. If every senator supports the new law the president has nothing to do but to approve it. Otherwise he can reject it and send back to senate for law improvements.

It is evident, that just elected president Honestman dislikes such situation. So he starts to struggle against the jobbery. And first of all he wants to put to jail the most dangerous senate members. And definitely, if senator is able to make even the harmful law approved, he is a dangerous one. So secret service of Martian president has already checked safes of each senate member, and found out on whom each of them has the goods. Martian president knows about your achievements in programming and he asks you personally for a help.

Input

The first line of input contains single integer N — the number of senate members (1 ≤ N ≤ 2000). Each senate member is uniquely identified with a number from 1 to N. Each of subsequent N lines contains information about senate members. The i-th line contains list of senate members (given by numeric identifiers) on whome he has the goods. List is terminated by number 0.

Output

Print the list of identifiers of all dangerous senate members in a single line. The numbers in the list must be present in increasing order. The list must be terminated by number 0.

Example

input output

5

3 2 0

4 5 0

1 5 0

2 0

1 3 4 0

题意：找出唯一的入度为零的缩点，否则输出0

思路：

这题目表意真的有够模糊的。。。知道后就直接套模板就行了。缩点处理完后，计算入度，最后看看统计入度为0的个数，以及缩点包含的点即可

AC代码：

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e4+500;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };

vector<vector<ll> > D(maxn);
ll dfn[maxn], low[maxn], vis[maxn], s[maxn], cnt[maxn], sum=0, idx = 0 , color[maxn];
ll up = 0;
ll n,m;
ll du[maxn];
vector<vector<ll>  >  res(maxn);
ll ans[maxn];
void init()     //初始化
{
    mem(dfn,0);mem(low,0);mem(vis,0);mem(s,0);
    mem(cnt,0);mem(color,0);mem(du,0);
    for(int i=1;i<=n;i++) D[i].clear();
    sum = idx = up = 0;
}

void Tarjan(ll u)
{
    dfn[u] = low[u] = ++idx;
    vis[u] = 1; s[++up] = u;
    for(int i=0;i<D[u].size();i++)
    {
        int v = D[u][i];
        if(!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else
        {

            if(vis[v]) low[u] = min(low[u],low[v]);
        }
    }
    if(dfn[u]==low[u])
    {
        color[u] = ++sum;
        vis[u] = 0;
        while(s[up] != u)
        {
            color[s[up]] = sum;
            vis[s[up--]] = 0;
        }
        up--;
    }
}

int main()
{
        n = read();
        init();
        rep(i,1,n)
        {
            ll x,y;
            x = i;
            while(1)
            {
                y = read();
                if(!y) break;
                D[x].pb(y);
            }

        }
        rep(i,1,n) if(dfn[i]==0) Tarjan(i);

        rep(i,1,n)
        {
            for(int j=0;j<D[i].size();j++)
            {
                ll v = D[i][j];
                if(color[v]!=color[i]) du[color[v]] ++ ;

            } res[color[i]].pb(i);
            cnt[color[i]] ++;
        }

        ll pos = 0;
        ll num = 0;
        rep(i,1,sum)
        {

            if(du[i]==0)
            {   num ++;
                if(num==1)
                for(int j=0;j<res[i].size();j++)
                ans[pos++] = res[i][j];
            }
        }
        if(num!=1)
        {
            printf("0\n");
            return 0;
        }
        sort(ans,ans+pos);
        rep(i,0,pos-1) cout<<ans[i]<<' ';
        cout<<0<<'\n';

    return 0;
}