大家好，又见面了，我是全栈君。
题意：给定一个n个点的连通的无向图。一个点的“鸽子值”定义为将它从图中删去后连通块的个数。
求“鸽子值”按降序排列的前m个。
思路：事实上题目就是要用来寻找割顶，我们仅仅需找出割顶。然后记录这个割顶属于几个不同连通分量的公共点，不是割点的，去掉之后。图的连通块数为1。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 10005;
struct node{
int id, val;
}b[MAXN];
int n, m;
int pre[MAXN], low[MAXN], dfs_clock;
vector<int> g[MAXN];
void init() {
for (int i = 0; i < n; i++)
g[i].clear();
for (int i = 0; i < n; i++) {
b[i].id = i;
b[i].val = 1;
}
}
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++;
}
}
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;
}
void find_bcc(int n) {
memset(pre, 0, sizeof(pre));
memset(low, 0, sizeof(low));
dfs_clock = 0;
for (int i = 0; i < n; i++)
if (!pre[i])
dfs(i, -1);
}
int main() {
while (scanf("%d%d", &n, &m)) {
if (n == 0 && m == 0)
break;
init();
int u, v;
while (scanf("%d%d", &u, &v)) {
if (u == -1 && v == -1)
break;
g[u].push_back(v);
g[v].push_back(u);
}
find_bcc(n);
sort(b, b + n, cmp);
for (int i = 0; i < m; i++)
printf("%d %d\n", b[i].id, b[i].val);
puts("");
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115689.html原文链接：https://javaforall.net
