uva 10765 Doves and Bombs（割顶）



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

思路dfs检查每一个点是否为割顶，并标记除去该点后有多少个连通分量

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#define eps 1e-6
#define LL long long
using namespace std;  const int maxn = 10000 + 100;
const int INF = 0x3f3f3f3f;
int n, m;
vector<int> G[maxn];
int val[maxn], node[maxn]; //node数组记录结点id间接排序
bool cmp(int x, int y) {
return val[x] == val[y] ? x < y : val[x] > val[y];
}int pre[maxn], dfs_clock;
int dfs(int u, int fa) { //u在dfs树中的父节点为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]) {   //没有訪问过v
child++;
int lowv = dfs(v, u);
lowu = min(lowu, lowv);    //用后代的low函数更新u的low函数
if(lowv >= pre[u]) {
val[u]++;
}}
else if(pre[v] < pre[u] && v != fa)  lowu = min(lowu, pre[v]);  //用反向边更新u的low函数
}
if(fa < 0 && child == 1) val[u] = 1;
return lowu;
} void init() {
dfs_clock = 0;
memset(pre, 0, sizeof(pre));
for(int i = 0; i < n; i++) {
G[i].clear();
node[i] = i;
val[i] = 1;
}
int x, y;
while(scanf("%d%d", &x, &y) == 2 && x >= 0) {
G[x].push_back(y);
G[y].push_back(x);
}
}void solve() {
dfs(0, -1);
sort(node, node+n, cmp);
for(int i = 0; i < m; i++) cout << node[i] << " " << val[node[i]] << endl;
cout << endl;
}int main() {
//freopen("input.txt", "r", stdin);
while(scanf("%d%d", &n, &m) == 2 && n) {
init();
solve();
}
return 0;
}