题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1213
题意 给出N个人 M对关系 找出共有几对连通块
思路 并查集
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 = 5e4 + 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 t; cin >> t; while (t--) { init(); int n, m; scanf("%d%d", &n, &m); int x, y; for (int i = 0; i < m; i++) { scanf("%d%d", &x, &y); join(x, y); } map <int, int> M; for (int i = 1; i <= n; i++) M[find(i)]++; cout << M.size() << endl; } }转载于:https://www.cnblogs.com/Dup4/p/9433108.html
