题意:
给了一个联通无向图...现在问去掉某个点..会让图变成几个联通块?...输出的..按分出的从多到小..若相等..输出标号从小到大.输出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;
}