题意
给出 N 对 数字 然后 每次从一对中 取出一个数字 判断 能否有一种取出的方案 取出的每个数字 都是不同的
思路 将每一对数字 连上一条边 然后 最后 判断每一个连通块里面 边的个数 是否 大于等于 点的个数 用并查集判断
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> 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; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-6; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 5; const int MOD = 1e9 + 7; int pre[maxn]; int find(int x) { int r = x; while (pre[r] != r) r = pre[r]; int j = x, i; while (j != r) { i = pre[j]; pre[j] = r; j = i; } return r; } void join(int x, int y) { int fx = find(x), fy = find(y); if (x != fy) pre[fx] = fy; } int p[maxn], q[maxn]; struct Node { map <int, int> M; int tot; }; int main() { int t; cin >> t; while (t--) { int n; scanf("%d", &n); for (int i = 0; i < maxn; i++) pre[i] = i; for (int i = 0; i < n; i++) { scanf("%d%d", &p[i], &q[i]); join(p[i], q[i]); } map <int, Node> m; int flag = 1; for (int i = 0; i < n; i++) { int num = find(p[i]); m[num].M[q[i]] = 1; m[num].M[p[i]] = 1; m[num].tot ++; if (m[num].M.size() < m[num].tot) { flag = 0; break; } } if (flag) printf("possible\n"); else printf("impossible\n"); } }转载于:https://www.cnblogs.com/Dup4/p/9433242.html
