学步园

     JX大大刚接触并查集(想起当年向总当年的那口音..beng查集)...纠结了这道题....我在无聊水USACO的时候也来瞅了瞅这题...

     去年多校联合武汉大学出的...题意是说给一个无向图...有哪些连通分量...并且有那些连通分量是环(这道题的环是指这个连通分量首尾相连没有多余的边)...

      既然是无向图...那么能通过边直接或间接到达的就是一个连通分量..其实也就是并查集了..读边的时候同时做并查集操作...最后扫描所有的点就得到了集合的数量..

      既然要只能首尾相连的一个连通分量才是环...那么实际上就是指这个连通分量里所有点的度为2...在读边的时候就可以对度进行累加了..再判断一下去掉有度不为2的点的连通分量...就是第二问的答案...

Program:

#include<iostream>
#define MAXN 100001
using namespace std;
struct node
{
    int x,y;      
}line[MAXN*3];
int n,m,father[MAXN],link[MAXN],ans,i;
int getfather(int k)
{
    if (father[k]==k) return k;
    return father[k]=getfather(father[k]);  
}
bool f[MAXN];
int main()
{ 
    while(~scanf("%d%d",&n,&m))
    {
          if (!n && !m) break;
          for (i=0;i<n;i++) father[i]=i;
          memset(link,0,sizeof(link));
          for (i=1;i<=m;i++)
          { 
               scanf("%d%d",&line[i].x,&line[i].y);  
               link[line[i].x]++; link[line[i].y]++; 
               father[getfather(line[i].y)]=getfather(line[i].x);       
          }   
          memset(f,false,sizeof(f));
          ans=0;
          for (i=0;i<n;i++)
          if (!f[getfather(i)]) 
          {
               f[father[i]]=true;
               ans++;                   
          }           
          printf("%d ",ans);
          for (i=0;i<n;i++)
             if (link[i]!=2) f[father[i]]=false;
          ans=0;
          for (i=0;i<n;i++)
             if (f[i]) ans++;
          printf("%d\n",ans);
    }
    return 0;   
}

.