题意： 众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：
给出一张 n 个点 n+1 条边的无向图，你可以选择一些边（至少一条）删除。
现在勇太想知道有多少种方案使得删除之后图依然联通。
当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？
解法： n个点，n+1条边，显然你最多就只能删除两个点让他成为一棵树
所以我们就直接暴力枚举两个点就好了，然后我们再用并查集去check一下
//HDU 5631#include <bits/stdc++.h>using namespace std;const int maxn = 150;int n;pair <int, int> p[maxn];namespace dsu{ int fa[maxn]; inline void init(){for(int i = 1; i <= n; i++) fa[i] = i;} inline int find_set(int x){if(x == fa[x]) return x; return fa[x] = find_set(fa[x]);} inline void union_set(int x, int y){x = find_set(x), y = find_set(y); if(x != y) fa[x] = y;}}using namespace dsu;int main(){ int t; scanf("%d", &t); while(t--){ scanf("%d", &n); for(int i = 1; i <= n + 1; i++) scanf("%d%d", &p[i].first, &p[i].second); int ans = 0; //1 for(int i = 1; i <= n + 1; i++){ for(int j = 1; j <= n; j++) fa[j] = j; for(int j = 1; j <= n + 1; j++){ if(i == j) continue; union_set(p[j].first, p[j].second); } int ok = 1; for(int j = 1; j <= n; j++){ if(find_set(j) != find_set(fa[1])) ok = 0; } if(ok) ans++; } //2 for(int i = 1; i <= n + 1; i++){ for(int j = i + 1; j <= n + 1; j++){ for(int k = 1; k <= n; k++) fa[k] = k; for(int k = 1; k <= n + 1; k++){ if(k == i || k == j) continue; union_set(p[k].first, p[k].second); } int ok = 1; for(int k = 1; k <= n; k++){ if(find_set(k) != find_set(fa[1])) ok = 0; } if(ok) ans++; } } PRintf("%d/n", ans); } return 0;}新闻热点
疑难解答
