题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1272
思路 只需要判断 这张图 无环 并且只有一个连通块 就可以了
要注意 如果 只输入 0 0 那给的是空图 要给出 Yes
判断 无环 有两个方法
0.在并查集的合并操作中 如果 find(x) == find(y) 就说明 x 和 y 已经有一条边了 再加 就是成环了 直接 flag = 0 1.我们可以对边的个数 计数 只有 边数== 结点个数-1 才是满足条件的
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 10; const int MOD = 1e9 + 7; int pre[maxn]; int find(int x) { int r = x; while (pre[r] != r) r = pre[r]; int i = x, j; while (i != r) { j = pre[i]; pre[i] = r; i = j; } return r; } void join(int x, int y) { int fx = find(x), fy = find(y); if (x != fy) pre[fx] = fy; } void init() { for (int i = 0; i < maxn; i++) pre[i] = i; } int main() { int x, y; set <int> s; s.clear(); int edge = 0; init(); while (scanf("%d%d", &x, &y)) { if (x == -1 && y == -1) break; else if ((x || y)) { edge++; s.insert(x); s.insert(y); join(x, y); } else { if (edge == 0) { printf("Yes\n"); continue; } map <int, int> m; int len = s.size(); while (!s.empty()) { int num = find(*s.begin()); s.erase(s.begin()); m[num]++; } int flag = 1; if (edge != len - 1 || m.size() != 1) flag = 0; if (flag) printf("Yes\n"); else printf("No\n"); s.clear(); edge = 0; init(); } } }AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 10; const int MOD = 1e9 + 7; int pre[maxn]; int flag; int find(int x) //路径压缩 { int r = x; while (pre[r] != r) r = pre[r]; int i = x, j; while (i != r) { j = pre[i]; pre[i] = r; i = j; } return r; } //int find(int x) //{ // while (x != pre[x]) // x = pre[x]; // return x; //} void join(int x, int y) { int fx = find(x), fy = find(y); if (fx != fy) pre[fx] = fy; else flag = 0; } void init() { for (int i = 0; i < maxn; i++) pre[i] = i; } int main() { int x, y; set <int> s; s.clear(); init(); flag = 1; while (scanf("%d%d", &x, &y)) { if (x == -1 && y == -1) break; else if ((x || y)) { s.insert(x); s.insert(y); join(x, y); } else { if (s.size() == 0) { printf("Yes\n"); continue; } map <int, int> m; int len = s.size(); while (!s.empty()) { int num = find(*s.begin()); s.erase(s.begin()); m[num]++; } if (m.size() != 1) flag = 0; if (flag) printf("Yes\n"); else printf("No\n"); s.clear(); init(); flag = 1; } } }转载于:https://www.cnblogs.com/Dup4/p/9433107.html
