codevs2822

解题思路： tarjan缩点后算出度为0的点有几个，如果只有一个且这个点为爱心天使就行了；

#include<iostream>

#include<algorithm>

#include<vector>

#include<queue>

#include<cstdio>

#include<cstring>

#define maxn 10005

using namespace std;

struct node

{

    int x;

    int y;

}a[maxn];

struct Edge

{

    int to;

    int next;

}edge[maxn];

int low[maxn];

int dfn[maxn];

int instack[maxn];

int visit[maxn];

int sccno[maxn];

int outdegree[maxn];

int cnt;

int step;

int indexx;

int scc_cnt;

int head[maxn];

vector<int>scc[maxn];

void add(int u,int v)

{

    edge[cnt].next=head[u];

    edge[cnt].to=v;

    head[u]=cnt++;

    return;

}

void tarjan(int u)

{

    low[u]=dfn[u]=++step;

    instack[++indexx]=u;

    visit[u]=1;

    for(int i=head[u];i!=-1;i=edge[i].next)

    {

        if(!dfn[edge[i].to])

        {

            tarjan(edge[i].to);

            low[u]=min(low[u],low[edge[i].to]);

        }

        else if(visit[edge[i].to])

        {

            low[u]=min(low[u],dfn[edge[i].to]);

        }

    }

    if(low[u]==dfn[u])

    {

        scc_cnt++;

        scc[scc_cnt].clear();

        do

        {

            scc[scc_cnt].push_back(instack[indexx]);

            sccno[instack[indexx]]=scc_cnt;

            visit[instack[indexx]]=0;

            indexx--;

        }

        while(u!=instack[indexx+1]);

    }

    return;

}

void init()

{

    memset(head,-1,sizeof(head));

    cnt=step=indexx=scc_cnt=0;

    memset(visit,0,sizeof(visit));

    memset(low,0,sizeof(low));

    memset(dfn,0,sizeof(dfn));

    return ;

}

int main()

{

    int n,m;

    int x,y;

    init();

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)

    {

        scanf("%d%d",&a[i].x,&a[i].y);

        add(a[i].x,a[i].y);

    }

    for(int i=1;i<=n;i++)

        if(!dfn[i])

        tarjan(i);

    for(int i=1;i<=n;i++)

    {

        if(sccno[a[i].x]!=sccno[a[i].y])

            outdegree[sccno[a[i].x]]++;

    }

    int flag=0;

    int pos;

    for(int i=1;i<=scc_cnt;i++)

    {

        if(outdegree[i]==0)

        {

            flag++;pos=i;

        }

    }

    int ans=0;

    for(int i=1;i<=scc_cnt;i++)

    {

        if(scc[i].size()>1)

            ans++;

    }

    cout<<ans<<endl;

        if(flag==1)

        {

            if(scc[pos].size()>1)

            {

                sort(scc[pos].begin(),scc[pos].end());

                for(int i=0;i<scc[pos].size();i++)

                    cout<<scc[pos][i]<<" ";

            }

            else

                cout<<"-1\n";

        }

        else

            cout<<"-1\n";

    return 0;

}