HackerRank - journey-to-the-moon 【并查集】
题意 有很多不同的宇航员，有些宇航员来自同一个国家，有些宇航员来自不同的国家，然后美国航天局想要选出两名来自不同国家的宇航员，求出最大的选法。然后 数据一对一对的给出 给出的说明这两人是来自同一个国家的。
思路 使用并查集并压缩路径，然后最后在MAP 里面存放的就是 有几个“祖先”，并且这个祖先里面下属加上它一共有多少人
然后求不同的人数 就是排列组合
AC代码
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #include <ctype.h> #include <numeric> #include <sstream> using namespace std; typedef long long LL; const double PI = 3.14159265358979323846264338327; const double E = 2.718281828459; const int MAXN = 0x3f3f3f3f; const int MINN = 0xc0c0c0c0; const int maxn = 1e5 + 5; int pre[maxn]; int find(int x) { int r = x; while (pre[r] != r) r = pre[r]; pre[x] = r; return r; } void join(int x, int y) { int fx = find(x), fy = find(y); if (x != fy) pre[fx] = fy; } int main() { int n, m; int a, b; int i; map <int, int> q; q.clear(); scanf("%d %d", &n, &m); for (i = 0; i < n; i++) pre[i] = i; for (i = 0; i < m; i++) { scanf("%d%d", &a, &b); join(a, b); } LL tot = 0; LL sum = 0; for (i = 0; i < n; i++) { q[find(i)] ++; sum ++; } map <int, int>::iterator it; for (it = q.begin(); it != q.end(); it++) { sum -= it -> second; tot += (it -> second) * sum; } printf("%lld\n", tot); }转载于:https://www.cnblogs.com/Dup4/p/9433390.html
相关资源：JAVA上百实例源码以及开源项目