学步园

           题意:

                    给了一个联通无向图...现在问去掉某个点..会让图变成几个联通块?...输出的..按分出的从多到小..若相等..输出标号从小到大.输出M个...

           题解:

                    从求割点的过程演变得出一个点去掉会将图变成几个联通块..

                    也就是在做tarjan时...当一个边dfn[u]<=low[v]时..其分成的块个数++..但值得注意的同样是一个联通快第一个进去的点.个数要-1...

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include <stack>
#include<queue>
#include<algorithm>
#include<cmath>
#define oo 1000000007
#define ll long long
#define pi acos(-1.0)
#define MAXN 10005
#define MAXM 500505
using namespace std;     
struct node
{
      int v,u,id,next; 
}edge[MAXM];
struct NODE
{
      int id,num;
}ans[MAXN];
int Ne,_next[MAXN],dfn[MAXN],DfsIndex,low[MAXN]; 
set<int> Ans[MAXN];
void addedge(int u,int v,int id)
{
      edge[++Ne].next=_next[u],_next[u]=Ne;
      edge[Ne].u=u,edge[Ne].v=v,edge[Ne].id=id;
}
void tarjan(int u,int id)  
{  
      dfn[u]=low[u]=++DfsIndex;   
      ans[u].id=u,ans[u].num=1;
      for (int k=_next[u];k;k=edge[k].next)  
         if (edge[k].id!=id)  
         {  
                int v=edge[k].v;      
                if (!dfn[v])  
                {  
                       tarjan(v,edge[k].id);  
                       low[u]=min(low[u],low[v]);  
                       if (dfn[u]<=low[v]) ans[u].num++;  
                }else  
                       low[u]=min(low[u],dfn[v]);  
        }   
}  
bool cmp(NODE a,NODE b)
{
      if (a.num!=b.num) return a.num>b.num;
      return a.id<b.id;
}
int main()
{      
      int u,v,n,m,id,i;  
      while (scanf("%d%d",&n,&m) && n && m)
      {
               Ne=id=0,memset(_next,0,sizeof(_next));
               while (scanf("%d%d",&u,&v) && u!=-1)
                   addedge(u,v,++id),addedge(v,u,id);
               memset(dfn,0,sizeof(dfn));  
               DfsIndex=0;
               for (u=0;u<n;u++)
                  if (!dfn[u]) 
                  {     
                         tarjan(u,0); 
                         ans[u].num--;
                  }   
               sort(ans,ans+n,cmp); 
               for (i=0;i<m;i++) printf("%d %d\n",ans[i].id,ans[i].num); 
               puts("");
      }
      return 0;
}