【codevs2822】爱在心中

题目描述 Description

输入描述 Input Description

输出描述 Output Description

样例输入 Sample Input

样例输出 Sample Output

【题解】

第一问的答案就是缩点后长度大于1的环的数量。

第二问：注意到一点：缩点后满足条件的点一定是出度为0，那么就好办了，遍历每个点，如果出度为零，记录下来，然后去找。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<ctime>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 #define MAXN 50010

 struct node{int y,next;}e[MAXN],e2[MAXN];

 int n,m,now,len,top,bcnt,Link[MAXN],Link2[MAXN],dfn[MAXN],low[MAXN],instack[MAXN],stack[MAXN],belong[MAXN],size[MAXN];

 inline int read()

 {

     int x=,f=;  char ch=getchar();

     while(!isdigit(ch))  {if(ch=='-')  f=-;  ch=getchar();}

     while(isdigit(ch))  {x=x*+ch-'';  ch=getchar();}

     return x*f;

 }

 void insert(int x,int y)  {e[++len].next=Link[x];Link[x]=len;e[len].y=y;}

 void Insert(int x,int y)  {e2[++len].next=Link2[x];Link2[x]=len;e2[len].y=y;}

 void tarjan(int x)

 {

     dfn[x]=low[x]=++now;

     instack[x]=;  stack[++top]=x;

     for(int i=Link[x];i;i=e[i].next)

     {

         if(!dfn[e[i].y])

         {

             tarjan(e[i].y);

             low[x]=min(low[x],low[e[i].y]);

         }

         else if(instack[e[i].y])  low[x]=min(low[x],dfn[e[i].y]);

     }

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

     {

         int y;  bcnt++;

         do

         {

             y=stack[top--];

             instack[y]=;

             belong[y]=bcnt;

             size[bcnt]++;

         }while(x!=y);

     }

 }

 int main()

 {

     //freopen("cin.in","r",stdin);

     //freopen("cout.out","w",stdout);

     n=read();  m=read();

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

     {

         int x=read(),y=read();

         insert(x,y);

     }

     len=;

     for(int i=;i<=n;i++)  if(!dfn[i])  tarjan(i);

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

         for(int j=Link[i];j;j=e[j].next)

             if(belong[e[j].y]!=belong[i])

                 Insert(belong[i],belong[e[j].y]);

     int ans=;

     for(int i=;i<=bcnt;i++)

         if(size[i]>)  ans++;

     printf("%d\n",ans);

     ans=-;

     for(int i=;i<=bcnt;i++)

         if(!Link2[i])

         {

             if(ans!=-||size[i]==)  {ans=-;  break;}

             else ans=i;

         }

     if(ans==-)  {printf("-1\n");  return ;}

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

         if(belong[i]==ans)  printf("%d ",i);

     printf("\n");

     return ;

 }