UVA - 10765 Doves and bombs (点双连通分量)

题意：给定一个n个点的连通无向图，一个点的鸽子值定义为将它从图中删去后连通块的个数。求每个点的鸽子值。

分析：其实就是求割项，然后统计每个割项属于多少个块，注意输出的顺序，题目要求输出m个，鸽子值大的先输出，如果鸽子值相同，则按照节点序号升序输出，所以要sort排一下序。另外输出的不一定是割点，如果不是割点，去掉后块的个数为1（图本身算一个块），所以每个节点的鸽子值要初始化为1

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define MAXN 10010
using namespace std;


struct node{
    int id, val;//节点序号和鸽子值
}b[MAXN];

int dfs_clock;
int n, m,x, y;
int pre[MAXN], low[MAXN];
vector<int> G[MAXN];

bool cmp(node a, node b){
if(a.val == b.val) return a.id<b.id;
return a.val>b.val;
}

int dfs(int u, int fa){
int lowu = pre[u] = ++dfs_clock;
int child = 0;
for(int i = 0; i<G[u].size(); i++){
int v = G[u][i];
if(!pre[v]){
child++;
int lowv = dfs(v, u);
lowu = min(lowu, lowv);
if(lowv >= pre[u]){
b[u].val++;//如果是割点，鸽子值从1开始自增
}
}
else if(pre[v] < pre[u] && v!=fa){
lowu = min(lowu, pre[v]);
}
}
if(fa<0 && child==1) b[u].val = 1;//根节点
low[u] = lowu;
return lowu;
} 

int main(){
while(scanf("%d %d", &n, &m) && n){
for(int i = 0; i<n; i++) {
    G[i].clear();
    b[i].val = 1;
    b[i].id = i;
}
memset(pre, 0, sizeof(pre));
memset(low, 0,sizeof(low));
dfs_clock=0;

while(scanf("%d %d", &x, &y) && x!=-1){
G[x].push_back(y);
G[y].push_back(x);
}

for(int i = 0; i<n; i++){
if(!pre[i]) dfs(i, -1);
} 
sort(b,b+n,cmp);
for(int i=0;i<m;i++){
printf("%d %d\n", b[i].id, b[i].val);
}
printf("\n");
}
return 0;
}