题目链接
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3761
题意
在一个桌面上，给出一些球 如果在A球的某个方向的前方有B球 那个A球就可以朝那个方向滚 然后 滚到B球的位置后 ，B球往前滚，A球停在B球的位置上
求这样操作后，最后最少剩下多少球，然后要输出操作的方式
思路
其实可以发现，一个球经过一次操作之后，相当于这个球消失了 因为它替代了它前方那个球的位置 这个操作又迭代下去
最后发现 其实只有这个球本身的位置是没有球了
所以 如果一个球的四周有球 这个球就可以消失
那么 我们可以把一个球的四个方向上的球都并起来，然后并起来的球的四个方向的球又可以并起来，最后剩下的球的个数 其实就是连通块的个数
这个 并 我们只需要指向父节点就可以了 而不需要指向祖先节点，因为操作方式中 就是将这个球打向父节点，而不是祖先节点，因为和祖先节点并不一定是在同一个方向上的
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 <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); #define fi first #define se second //#define bug //#define gets gets_s 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; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 2e3 + 10; const int MOD = 1e9 + 7; int pre[maxn]; int tot[maxn]; 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; } int n; int G[maxn][maxn]; int x[maxn], y[maxn]; bool judge(int a, int b) { if (x[a] == x[b] || y[a] == y[b]) return true; return false; } void dfs(int root, int vis) { for (int i = 1; i <= n; i++) { if (G[root][i] == 1 && pre[i] == i && root != i && i != vis) { pre[i] = root; dfs(i, vis); } } } void clear() { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) G[i][j] = 0; for (int i = 1; i <= n; i++) { pre[i] = i; tot[i] = 0; } } void print(int root, int son) { if (x[root] == x[son]) puts(y[root] > y[son] ? "UP" : "DOWN"); else puts(x[root] > x[son] ? "RIGHT" : "LEFT"); } int main() { while (~scanf("%d", &n)) { clear(); for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]); for (int i = 1; i <= n; i++) { G[i][i] = 1; for (int j = i + 1; j <= n; j++) { if (judge(i, j)) G[i][j] = G[j][i] = 1; } } //for (int i = 1; i <= n; i++) // for (int j = 1; j <= n; j++) // printf("%d%c", G[i][j], j == n ? '\n' : ' '); for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { if (G[i][j] && pre[j] == j) { pre[j] = i; dfs(j, i); } } } map <int, int> m; for (int i = 1; i <= n; i++) { int u = find(i); m[u]++; } for (int i = 1; i <= n; i++) tot[pre[i]]++; printf("%d\n", m.size()); int pos = 1; int len = n - m.size(); while (pos <= len) { for (int i = 1; i <= n && pos <= len; i++) { int root = pre[i]; if (i != root && tot[i] == 0) { printf("(%d, %d) ", x[i], y[i]); print(root, i); tot[root]--; tot[i]--; pos++; } } } } }转载于:https://www.cnblogs.com/Dup4/p/9433084.html
相关资源：JAVA上百实例源码以及开源项目