大家好,又见面了,我是全栈君。
题意:给定一个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; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115689.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...