codevs2822爱在心中

#include<iostream>
#include<cstdio>
using namespace std;
#define N 202020
struct Edge
{
    int x,y,next;
    Edge(int x=0,int y=0,int next=0):
        x(x),y(y),next(next){}
}edge[N];
int sumedge,tim,an,js,top,sumclr,ann,n,m;
int head[N],low[N],dfn[N],Stack[N],cnt[N],color[N],cd[N],x[N],y[N];
bool instack[N];
int ins(int x,int y)
{
    edge[++sumedge]=Edge(x,y,head[x]);
    return head[x]=sumedge;
}
void tarjan(int x)
{
    Stack[++top]=x;instack[x]=1;
    low[x]=dfn[x]=++tim;
    for(int u=head[x];u;u=edge[u].next)
    if(instack[edge[u].y])
    low[x]=min(low[x],dfn[edge[u].y]);
    else
    if(!dfn[edge[u].y])
    {
        tarjan(edge[u].y);
        low[x]=min(low[x],low[edge[u].y]);
    }
    else
    {}
    if(low[x]==dfn[x])
    {
        sumclr++;
        while(Stack[top+1]!=x)//top+1保证x出去。 
        {
            color[Stack[top]]=sumclr;
            instack[Stack[top]]=false;
            cnt[sumclr]++;
            top--;
        }
    }
}
int main() 
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
    scanf("%d %d",&x[i],&y[i]);    
    ins(x[i],y[i]);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i])tarjan(i);//注意图可能b不连通。 
    for(int i=1;i<=m;i++)
    if(color[x[i]]!=color[y[i]])cd[color[x[i]]]++;//相当于缩点吧...统计出度。 
    for(int i=1;i<=sumclr;i++)if(!cd[i])an=i,js++;
    for(int i=1;i<=sumclr;i++)if(cnt[i]>1)ann++;//不能自爱。（好奇怪的样子） 
    printf("%d\n",ann);
    if(js==1&&cnt[an]>1)
    {
        for(int i=1;i<=n;i++)
        if(color[i]==an)
        printf("%d ",i);
    }
    else
    puts("-1");
    return 0;    
}

//恨在心中 
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
#define N 202020
struct Edge
{
    int x,y,next;
    Edge(int x=0,int y=0,int next=0):
        x(x),y(y),next(next){}
}edge[N<<1];
int sumedge,sumedge2,x,y,n,m,tim,top,sumclr,js,ans;
int head[N],head2[N],low[N],dfn[N],color[N],Stack[N],out[N],tmp[N],cnt[N];
bool instack[N],vis[N],can[N];
map<int,bool>Map[N];
vector<int>vec[N];
int ins(int x,int y)
{
    edge[++sumedge]=Edge(x,y,head[x]);
    return head[x]=sumedge;
}
int ins2(int x,int y)
{
    edge[++sumedge2]=Edge(x,y,head2[x]);
    return head2[x]=sumedge2;
}
void dfs(int x)
{
    vis[x]=1;
    low[x]=dfn[x]=++tim;
    instack[x]=1;Stack[++top]=x;
    for(int u=head[x];u;u=edge[u].next)
    if(instack[edge[u].y])
    low[x]=min(low[x],dfn[edge[u].y]);
    else
    if(!vis[edge[u].y])
    {
        dfs(edge[u].y);
        low[x]=min(low[x],low[edge[u].y]);
    }
    else
    {
    }
    if(low[x]==dfn[x])
    {
        sumclr++;color[x]=sumclr;
        vec[sumclr].push_back(x); 
        cnt[sumclr]++;
        while(Stack[top]!=x)
        {
            color[Stack[top]]=sumclr;
            instack[Stack[top]]=false;
            vec[sumclr].push_back(Stack[top]);
            top--;
            cnt[sumclr]++;
        }
        instack[x]=false;
        top--;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        ins(x,y);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        dfs(i);
    }
    int an=0;
    for(int i=1;i<=sumclr;i++)
    if(cnt[i]>1)an++;
     printf("%d\n",an);
    for(int i=1;i<=n;i++)
        for(int u=head[i];u;u=edge[u].next)
            if(color[i]!=color[edge[u].y])
            if(Map[color[i]].find(color[edge[u].y])==Map[color[i]].end())
            {
                Map[color[i]][color[edge[u].y]]=true;
                ins2(color[i],color[edge[u].y]);
                out[color[i]]++;
            }
    for(int i=1;i<=sumclr;i++)
    {
        if(out[i]==0)
        {
            js++;
            ans=i;
        }
    }
    if(js==1&&cnt[ans]>1)
    {
    for(int i=1;i<=n;i++)
    if(color[i]==ans)printf("%d ",i);
    }
    else
    puts("-1");
    return 0;
}