题目:
题意:
给了一个联通无向图,现在问去掉某个点,会让图变成几个联通块?
输出的按分出的从多到小,若相等,输出标号从小到大。输出M个。
分析:
BCC求割点后联通块数量,Tarjan算法。
联通块的数目在找到一个low[y]>=dfn[x]时累加,最后加一即可。
代码如下:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 10010 int n,m;
int first[Maxn],low[Maxn],dfn[Maxn],fa[Maxn],son[Maxn];
int cut[Maxn];
int cnt; struct node
{
int x,y,next;
};
node t[Maxn*],ans[Maxn];
int len; int mymin(int x,int y) {return x<y?x:y;} void ins(int x,int y)
{
t[++len].x=x;t[len].y=y;
t[len].next=first[x];first[x]=len;
} bool cmp(node x,node y) {return (x.x==y.x)?(x.y<y.y):(x.x>y.x);} void ffind(int x,int f)
{
dfn[x]=low[x]=++cnt;
fa[x]=f;
for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)
{
int y=t[i].y;
if(dfn[y]==)
{
ffind(y,x);
son[x]++;
low[x]=mymin(low[x],low[y]);
if(low[y]>=dfn[x]) cut[x]++;
}
else low[x]=mymin(low[x],dfn[y]);
}
} int main()
{
while()
{
scanf("%d%d",&n,&m);
if(n==&&m==) break;
len=;cnt=;
memset(first,,sizeof(first));
while()
{
int a,b;
scanf("%d%d",&a,&b);
if(a==-&&b==-) break;
a++;b++;
ins(a,b);ins(b,a);
}
memset(dfn,,sizeof(dfn));
memset(cut,,sizeof(cut));
memset(son,,sizeof(son));
ffind(,);ans[].y=;
if(son[]>) ans[].x=son[];
else ans[].x=;
for(int i=;i<=n;i++)
{
ans[i].y=i-;
ans[i].x=cut[i]+;
}
sort(ans+,ans++n,cmp);
for(int i=;i<=m;i++) printf("%d %d\n",ans[i].y,ans[i].x);
printf("\n");
}
return ;
}
[UVA10765]
2016-03-17 13:43:40