kuangbin带你飞 并查集 题解

题解"/>

kuangbin带你飞 并查集 题解

做这套题之前一直以为并查集是很简单的数据结构。

做了才发现自己理解太不深刻。只看重片面的合并集合。。

重要的时发现每个集合的点与这个根的关系，这个关系可以做太多事情了。

题解：

POJ 2236 Wireless Network

10S时限，尽量做到最优吧。一开始还怕会T

预处理出能到达的点。简单题看代码就行了

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 1010;
struct point
{double x,y;
}src[MAXN];
int fa[MAXN];
int Find(int x) {return x == fa[x] ? x : fa[x] = Find(fa[x]);}
bool repair[MAXN];
double dis[MAXN][MAXN];
vector<int>go[MAXN];int main()
{int N;double D;scanf("%d%lf",&N,&D);for (int i = 1 ; i <= N ; i++) scanf("%lf%lf",&src[i].x,&src[i].y);for (int i = 1 ; i <= N ; i++) go[i].clear();for (int i = 1 ; i <= N ; i++) fa[i] = i;for (int i = 1 ; i <= N ; i++){for (int j = i + 1 ; j <= N ; j++){dis[i][j] = sqrt((src[i].x - src[j].x) * (src[i].x - src[j].x) + (src[i].y - src[j].y) * (src[i].y - src[j].y));dis[j][i] = dis[i][j];if (dis[i][j] <= D) go[i].push_back(j);if (dis[i][j] <= D) go[j].push_back(i);}}memset(repair,false,sizeof(repair));char op[5];while (scanf("%s",op) != EOF){if(op[0] == 'O'){int x;scanf("%d",&x);repair[x] = true;for (int j = 0 ; j < (int)go[x].size() ; j++){if (repair[go[x][j]]){int fx = Find(x);int fy = Find(go[x][j]);if (fx != fy) fa[fx] = fy;}}}else{int x,y;scanf("%d%d",&x,&y);int fx = Find(x);int fy = Find(y);if (fx == fy) puts("SUCCESS");else puts("FAIL");}}return 0;
}

POJ 1611 The Suspects

有一个学校，有N个学生，编号为0-N-1，现在0号学生感染了非典，凡是和0在一个社团的人就会感染，并且这些人如果还参加了别的社团，他所在的社团照样全部感染，求感染的人数。

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 30010;
int fa[MAXN];
int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
int N,M;
int main()
{while (scanf("%d%d",&N,&M) != EOF){if (N == 0 && M == 0) break;for (int i = 0 ; i <= N ; i++) fa[i] = i;for (int i = 0 ; i < M ; i++){int cnt;scanf("%d",&cnt);int x;scanf("%d",&x);int fx = Find(x);for (int i = 1 ; i < cnt ; i++){int u;scanf("%d",&u);int fu = Find(u);if (fx != fu) fa[fu] = fx;}}int ret = 1;int need = Find(0);for (int i = 1 ; i < N ; i++){int fi = Find(i);if (fi == need) ret++;}printf("%d\n",ret);}return 0;
}

HDU 1213 How Many Tables
有几个集合

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 2010;
int fa[MAXN];
int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
int N,M;
bool vis[MAXN];int main()
{int T;scanf("%d",&T);while (T--){scanf("%d%d",&N,&M);memset(vis,false,sizeof(vis));for (int i = 0 ; i <= N ; i++) fa[i] = i;while (M--){int x,y;scanf("%d%d",&x,&y);int fx = Find(x);int fy = Find(y);if (fx != fy) fa[fx] = fy;}int ret = 0;for (int i = 1 ; i <= N ; i++)if (i == Find(i)) ret++;printf("%d\n",ret);}return 0;
}

HDU 3038 How Many Answers Are Wrong

第一次接触这类题目，一开始完全没想到要用并查集该怎么做，看了别人的代码才慢慢算是理解？

重要的是维护当前点，与当前点和他的跟之间的关系。这道题就变成了到他根的和为多少

我做这道题始终保持跟的下标是其集合内最小的

这道题的路径压缩是很好理解的。

重要的是怎么合并的两颗树。也就是unionset代码。看别人的这个代码困扰了我很久。最后自己手动代入才明白了一些

首先第一保证跟的下标是其集合内最小的 就是代码里要分论讨论的合并fa[x] = y的x和y 的关系

bool unionset(int x,int y,int val) { int a = Find(x); int b = Find(y); if (a == b) { return sum[y] - sum[x] == val; } if (a < b) { fa[b] = a; sum[b] = sum[x] + val - sum[y]; } else { fa[a] = b; sum[a] = sum[y] - val - sum[x]; } return true; }
首先sum[x]表示x到他的根的距离
代码中，对于a > b,在数轴上是这情况。1：b--a--x--y 那么fa[a] = b,就要求最左边那段的长度 就是by - xy - ax = ab
对于 a < b 在数轴上是这种情况 2：a--b--x--y 或者3： a--x--b--y 对于第一个情况使得fa[b] = a表示最左边的长度就是ax + xy - by = ab及代码中的sum[b] = sum[x] + val - sum[y];
对于另一种情况 求ab 等于 ax + xy - xy = ab 同样也是那个式子所以可以合并。那么合并集合就可以了

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 200010;
int fa[MAXN];
int sum[MAXN];
int Find(int x)
{if (x == fa[x]) return x;else{int tmp = fa[x];fa[x] = Find(fa[x]);sum[x] += sum[tmp];}return fa[x];
}bool unionset(int x,int y,int val)
{int a = Find(x);int b = Find(y);if (a == b){return sum[y] - sum[x] == val;}if (a < b){fa[b] = a;sum[b] = sum[x] + val - sum[y];}else{fa[a] = b;sum[a] = sum[y] - val - sum[x];}return true;
}int main()
{int N,M;while (scanf("%d%d",&N,&M) != EOF){int ret = 0;for (int i = 0 ; i <= N ; i++) fa[i] = i;memset(sum,0,sizeof(sum));while(M--){int x,y,val;scanf("%d%d%d",&x,&y,&val);if (!unionset(x - 1,y,val)) ret++;}printf("%d\n",ret);}return 0;
}

POJ 1182 食物链
这题目是并查集的超经典应用。
说难起始也难，说不难页不难。。！！
首先定义结构体。分别是他的父亲。和他与他这题目是并查集的超经典应用。父亲的关系
relat = 0 表示 其和其父亲是同类
relat = 1 表示 他的父亲吃他
relat = 2 表示 他吃他的父亲
那么初始化就所有值得父亲为他本身，显然他们之间的关系relat = 0本身和本身必然是同类
对于询问假话，如果2个在一个集合里。通过他们和父亲的关系就可以判断他们之间的relat关系来判断假话
第一步 ： 路径压缩如何更新
 这个你枚举一下就可以发现儿子和爷爷的relat值=(儿子与父亲的relat值+父亲与爷爷的relat值）%3 举个例子。儿子吃父亲 当前relat = 2，爷爷吃父亲,这个的relat = 1，这种情况
表示儿子和爷爷是同类。所以儿子和爷爷的关系是relat为何只考虑3层，考虑路径压缩压成了几层
第二步 ： 也是我觉得最困扰的如何合并集合。将2个树合并到一起
先给出代码

if (roota != rootb) { p[rootb].fa = roota; p[rootb].relat = (op - 1 + 6 + p[a].relat - p[b].relat) % 3; }

当前有a->roota ,b -> rootb a和b之间的op值。根据题意有op = 0，表示2者同类，op - 1是我们预先设置的状态值0，op = 2表示a吃b 。根据我们的设置op - 1 = 1表示父亲吃儿子
使得rootb的父亲是roota 那么相关的更新你可以这么看 把这4个点拉成一条链(首先我不知道这么做到底对不对。虽然AC了)
接下来由这张图来看。我们先求rootb和a之间的关系 由前面儿子和爷爷的结论 。我们快速得到这个值等于 （3 - relat[b]) % 3 + (3 - (OP - 1)) % 3
为什么这样注意：relat[b] 表示b和rootb的关系。不是rootb和b的关系。偏移量值需要改变。同理ab也一样。得到这个值后。这里就可以看做b不存在。三层中有roota--a--rootb
再利用这个公式就得到 (（3 - relat[b]) % 3 + (3 - (OP - 1)) % 3 + relat[a]) % 3 合并一下同余一下就得到了上面的合并的式子
最后判断假话
首先其一定在一个集合内。否则其必然是真话，因为遇到不在一个集合里就可以合并集合
第一种判断他们是不是同一类生物。这个直接判断和跟relat即可
另一种判断吃的关系同样也是你手动枚举一下就知道咋弄了。
代码：

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 50010;
struct node
{int fa;int relat;
}p[MAXN];int Find(int x)
{int tmp;if (x == p[x].fa) return x;tmp = p[x].fa;p[x].fa = Find(p[x].fa);p[x].relat = (p[x].relat + p[tmp].relat) % 3;return p[x].fa;
}int main()
{int N,K;int op;int ret = 0;scanf("%d%d",&N,&K);for (int i = 1 ; i <= N ; i++){p[i].fa = i;p[i].relat = 0;}for (int i = 1 ; i <= K ; i++){int a,b;scanf("%d%d%d",&op,&a,&b);if(a > N || b > N){ret++;continue;}if (op == 2 && a == b){ret++;continue;}int roota = Find(a);int rootb = Find(b);if (roota != rootb){p[rootb].fa = roota;p[rootb].relat = (op - 1 + 6 + p[a].relat - p[b].relat) % 3;}else{if(op == 1 && p[a].relat != p[b].relat){ret++;continue;}if (op == 2 && (3 - p[a].relat + p[b].relat) % 3 != 1){ret++;}}}printf("%d\n",ret);return 0;
}

POJ 1417 True Liars
并查集+背包dp
神只说真话，魔鬼直说假话。那就就发现一个很重要的事情！
只要回答yes那么2者同类，否则2者异类。这个不解释了
所以可以用并查集来维护点和根的关系。最后问是否方案数目唯一。于是这个就背包来维护
这个详情看代码吧

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 1010;
int fa[MAXN];
int val[MAXN];
bool vis[MAXN];
int Find(int x)
{if (x == fa[x]) return x;int tmp = fa[x];fa[x] = Find(fa[x]);val[x] = (val[x] + val[tmp]) % 2;return fa[x];
}
int N,P1,P2;
int cnt[MAXN][2];
int dp[MAXN][MAXN];
int pre[MAXN][MAXN];
vector<int>ans;
vector<int>res[MAXN][2];int main()
{while(scanf("%d%d%d",&N,&P1,&P2) != EOF){if (N == 0 && P1 == 0 && P2 == 0) break;for (int i = 0 ; i <= P1 + P2 ; i++){fa[i] = i;val[i] = 0;}for (int i = 0 ; i < N ; i++){int x,y;char op[10];scanf("%d%d%s",&x,&y,op);int fx = Find(x);int fy = Find(y);if (fx != fy){fa[fy] = fx;int tmp;if (op[0] == 'y') tmp = 0;else tmp = 1;val[fy] = val[x] + val[y] + tmp;}}memset(vis,false,sizeof(vis));memset(cnt,0,sizeof(cnt));for(int i = 0 ; i <= P1 + P2 ; i++){res[i][0].clear();res[i][1].clear();}int cas = 1;for (int i = 1 ; i <= P1 + P2 ; i++){if (vis[i]) continue;int fi = Find(i);//之前写错是因为i这个点不一定是根。我默认这点为跟了。下面就是错误的写法/*if (vis[i]) continue;vis[i] = true;int fi = Find(i);res[cas][0].push_back(i);cnt[cas][0]++;for (int j = i + 1 ; j <= P1 + P2 ; j++)*/for (int j = i ; j <= P1 + P2 ; j++){if (vis[j]) continue;int fj = Find(j);if (fj != fi) continue;vis[j] = true;res[cas][val[j]].push_back(j);cnt[cas][val[j]]++;}cas++;}memset(dp,0,sizeof(dp));cas--;/* for (int i = 1 ; i <= cas ; i++){for (int j = 0 ; j < (int)res[i][0].size(); j++)printf("%d ",res[i][0][j]);puts("");for (int j = 0 ; j < (int)res[i][1].size(); j++)printf("%d ",res[i][1][j]);puts("");printf("%d %d\n",cnt[i][0],cnt[i][1]);}*/dp[0][0] = 1;for (int i = 1 ; i <= cas ; i++){for (int j = P1 ; j >= 0 ; j--){if (j >= cnt[i][0] && dp[i - 1][j - cnt[i][0]] > 0){dp[i][j] += dp[i - 1][j - cnt[i][0]];if (dp[i][j] > 1) dp[i][j] = 2;pre[i][j] = j - cnt[i][0];}if (j >= cnt[i][1] && dp[i - 1][j - cnt[i][1]] > 0){dp[i][j] += dp[i - 1][j - cnt[i][1]];if (dp[i][j] > 1) dp[i][j] = 2;pre[i][j] = j - cnt[i][1];}}}if (dp[cas][P1] != 1){puts("no");continue;}ans.clear();int cur = P1;for (int i = cas ; i >= 1 ;i--){int pref = pre[i][cur];int sub = cur - pref;if (cnt[i][0] == sub){for (int j = 0 ; j < (int)res[i][0].size(); j++)ans.push_back(res[i][0][j]);}else{for (int j = 0 ; j < (int)res[i][1].size() ; j++)ans.push_back(res[i][1][j]);}cur = pref;}sort(ans.begin(),ans.end());for (int i = 0 ; i < (int)ans.size() ; i++)printf("%d\n",ans[i]);puts("end");}return 0;
}

POJ 1456 Supermarket
这个题数据这么小。怎么做都行。并查集就帮助你理解并查集
首先这是一个贪心
肯定优先选择大的完成。。贪心很明显，因为每个物品只需要执行一天，且全部都是一天
并查集维护点到根之间最近的可用的时间点是什么 ，根下标小与等于树上的点

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 10010;
int fa[MAXN];
int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
struct node
{int d,p;friend bool operator < (const node &a,const node &b){return a.p > b.p;}
}src[MAXN];
int N;int main()
{while (scanf("%d",&N) != EOF){for (int i = 0 ; i < N ; i++) scanf("%d%d",&src[i].p,&src[i].d);sort(src,src + N);for (int i = 0 ; i < MAXN ; i++) fa[i] = i;int ret = 0;for (int i = 0 ; i < N ; i++){int ti = Find(src[i].d);if (ti > 0){ret += src[i].p;fa[ti] = ti - 1;}}printf("%d\n",ret);}return 0;
}

POJ 1733 Parity game
同样询问假话在哪
并查集维护点到根之间1的个数是奇数还是偶数。有了前面的铺垫这里就很简单了。
val = 0 儿子到父亲之间为偶数个1，val = 1 儿子到父亲之间为奇数个1
第一：路径压缩 ： 直接儿子val异或父亲val值。
第二：合并集合 ： 直接全异或。
首先我保证 父亲的下标小于儿子。对于a,b之间的一个操作（奇数或者偶数）那么可能的情况是 fb--b--a--fa直接求fa到fb的奇偶性，无论什么情况直接val[b] ^ val[a] ^ ab即可对于其他数轴上的情况
一样的式子
代码：

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 10010;
int fa[MAXN],val[MAXN];
map<int,int>mp;
int L;
int u[MAXN],v[MAXN],ask[MAXN];
// val = 0  even val = 1 oddint Find(int x)
{if (x == fa[x]) return x;int tmp = fa[x];fa[x] = Find(fa[x]);val[x] = val[x] ^ val[tmp];return fa[x];
}int main()
{int N;int cas = 1;while (scanf("%d",&L) != EOF){mp.clear();scanf("%d",&N);int ans = N;for (int i = 0 ; i < N ; i++){scanf("%d%d",&u[i],&v[i]);if (u[i] > v[i]) swap(u[i],v[i]);u[i]--;if (!mp[u[i]]) mp[u[i]] = cas++;if (!mp[v[i]]) mp[v[i]] = cas++;char op[5];scanf("%s",op);if (op[0] == 'e') ask[i] = 0;else ask[i] = 1;}for (int i = 0 ;i < MAXN ; i++){fa[i] = i;val[i] = 0;}for (int i = 0 ; i < N ; i++){int l = mp[u[i]];int r = mp[v[i]];int fl = Find(l);int fr = Find(r);if (fl == fr){if ((val[l] ^ val[r]) != ask[i]){ans = i;break;}}else{fa[fr] = fl;val[fr] = val[l] ^ val[r] ^ ask[i];}}printf("%d\n",ans);}return 0;
}

POJ 1984 Navigation Nightmare
题很难读懂。这个题卡了我好久。我一直看别人代码十分费解。这个向量偏移，相对值到底该怎么理解
真是日了X了
这里都是相对长度，首先只分析南北方向。东西方向一样的分开分析
第一步：路径压缩：儿子相应长度值+=父亲相应长度值
第二部： 合并集合： 就这里我百思不得其解。
下面坐标全部指的是y坐标
首先保证根的坐标在节点坐标的下方。对于向北（上）方向的直线，认为他是正长度，否则为副长度
4个点 ： r1,r2,f1,f2 r1的根为f1,r2的根为f2
则有　　f2 到 f1 的长度 + r2 到 f2 的长度 =
　　　　r1 到 r2 的长度 + r1 到 f1 的长度 = 向量 r2-f1的长度
东西方向同理

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 40010;
int fa[MAXN];
int dx[MAXN],dy[MAXN];
int from[MAXN],to[MAXN],L[MAXN];
char dir[MAXN][5];
struct node
{int u,v;int index;int ti;friend bool operator < (const node &a,const node &b){return a.ti < b.ti;}
}src[MAXN];
int ans[MAXN];
int Find(int x)
{if (x == fa[x]) return x;int tmp = fa[x];fa[x] = Find(fa[x]);dy[x] += dy[tmp];dx[x] += dx[tmp];return fa[x];
}int main()
{int N,M;int Q;while (scanf("%d%d",&N,&M) != EOF){for(int i = 0 ; i <= N ; i++) fa[i] = i;memset(dx,0,sizeof(dx));memset(dy,0,sizeof(dy));for (int i = 1 ; i <= M ; i++){scanf("%d%d%d",&from[i],&to[i],&L[i]);scanf("%s",dir[i]);}scanf("%d",&Q);for (int i = 0 ; i < Q ; i++){scanf("%d%d%d",&src[i].u,&src[i].v,&src[i].ti);src[i].index = i;}sort(src,src + Q);int t = 1;for (int i = 0 ; i < Q ; i++){while (t <= M && src[i].ti >= t){int f1 = Find(from[t]);int f2 = Find(to[t]);if (f1 != f2){fa[f2] = f1;if (dir[t][0] == 'N'){dy[f2] = L[t] + dy[from[t]] - dy[to[t]];dx[f2] = dx[from[t]] - dx[to[t]];}else if (dir[t][0] == 'S'){dy[f2] = -L[t] + dy[from[t]] - dy[to[t]];dx[f2] = dx[from[t]] - dx[to[t]];}else if (dir[t][0] == 'E'){dx[f2] = L[t] + dx[from[t]] - dx[to[t]];dy[f2] = dy[from[t]] - dy[to[t]];}else{dx[f2] = -L[t] + dx[from[t]] - dx[to[t]];dy[f2] = dy[from[t]] - dy[to[t]];}}t++;}if (Find(src[i].u) != Find(src[i].v))  ans[src[i].index] = -1;else{ans[src[i].index] = abs(dx[src[i].u] - dx[src[i].v]) + abs(dy[src[i].u] - dy[src[i].v]);}}for (int i = 0 ; i < Q  ; i++) printf("%d\n",ans[i]);}return 0;
}

POJ 2492 A Bug's Life
给出交配行为，问是否同性可交配
默认每一次交配为异性，如果有冲突则满足有同性交配
同样和父亲的关系为同性 val值为0，否则为1

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 2010;
const int MAXD = 1000010;
int fa[MAXN];
int val[MAXN];int Find(int x)
{if (x == fa[x]) return x;int tmp = fa[x];fa[x] = Find(fa[x]);val[x] = val[x] ^ val[tmp];return fa[x];
}int main()
{// freopen("sample.txt","r",stdin);int T,N,M,kase = 1;bool first = true;scanf("%d",&T);while (T--){if (first) first = false;else putchar('\n');scanf("%d%d",&N,&M);for (int i = 0 ; i <= N ; i++){fa[i] = i;val[i] = 0;}bool flag = false;for (int i = 0 ; i < M ; i++){int u ,v;scanf("%d%d",&u,&v);if (flag) continue;int fu = Find(u);int fv = Find(v);if (fu == fv){int res = val[u] ^ val[v];if (res == 0){flag = true;}}else{fa[fv] = fu;val[fv] = val[u] ^ val[v] ^ 1;}}printf("Scenario #%d:\n",kase++);if (flag) puts("Suspicious bugs found!");else puts("No suspicious bugs found!");}return 0;
}

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 510;
int fa[MAXN];
int val[MAXN];int Find(int x)
{if (x == fa[x]) return x;int tmp = fa[x];fa[x] = Find(fa[x]);val[x] = (val[x] + val[tmp]) % 3;return fa[x];
}int N,M;
struct node
{int u,v;int op;
}src[4010];
char str[50];int main()
{while (scanf("%d%d",&N,&M) != EOF){gets(str);for (int i = 0 ; i < M ; i++){gets(str);int pos;int len = strlen(str);for (pos = 0 ; pos < len ; pos++) if (str[pos] == '=' || str[pos] == '>' || str[pos] == '<') break;int u = 0;for (int j = 0 ; j < pos ; j++){u = u * 10 + str[j] - '0';}int v = 0;for (int j = pos + 1 ; j < len ; j++){v = v * 10 + str[j] - '0';}src[i].u = u;src[i].v = v;if (str[pos] == '=') src[i].op = 0;else if (str[pos] == '<') src[i].op = 1;else src[i].op = 2;}// for (int i = 0 ; i < M ; i++)//  printf("%d %d %d\n",src[i].u,src[i].v,src[i].op);int ansi,anst = 0;int cnt = 0;for (int i = 0 ; i < N ; i++){for (int j = 0 ; j < N ; j++) fa[j] = j;memset(val,0,sizeof(val));int pos = -1;for (int j = 0 ; j < M ; j++){if (src[j].u == i || src[j].v == i) continue;int u = src[j].u;int v = src[j].v;int fu = Find(u);int fv = Find(v);if (fu == fv){if ((3 - src[j].op + val[u]) % 3 != val[v]){pos = j + 1;break;}}else{fa[fv] = fu;val[fv] = (6 - val[v] - src[j].op + val[u]) % 3;}}if (pos == -1){cnt++;ansi = i;}else anst = max(anst,pos);}if(cnt == 0)printf("Impossible\n");else if(cnt >= 2)printf("Can not determine\n");elseprintf("Player %d can be determined to be the judge after %d lines\n",ansi,anst);}return 0;
}

ZOJ 3261 Connections in Galaxy War

正向在线做的话有删除操作很难处理，就离线变成从后向前处理变为添加操作

就是普通并查集

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 10010;
const int MAXD = 50010;
int fa[MAXN];
int Find(int x) {return x == fa[x] ? x : fa[x] = Find(fa[x]);}
int val[MAXN],pos[MAXN];
void unionset(int u,int v)
{int fu = Find(u),fv = Find(v);if (fu != fv){fa[fu] = fv;if (val[fu] > val[fv]){val[fv] = val[fu];pos[fv] = pos[fu];}else if (val[fu] == val[fv] && pos[fu] < pos[fv]){pos[fv] = pos[fu];}}
}
int from[20010],to[20010];
map<int,int>mp[MAXN];
bool vis[20010];
int p[MAXN];
struct node
{int op;int u,v;
}ask[MAXD];
int ret[MAXD];int main()
{int N;bool first = true;while (scanf("%d",&N) != EOF){if (first) first = false;else puts("");for (int i = 0 ; i < N ; i++){scanf("%d",&p[i]);val[i] = p[i];pos[i] = i;mp[i].clear();}for (int i = 0 ; i <= N ; i++) fa[i] = i;int M;scanf("%d",&M);for (int i = 1 ; i <= M ; i++){scanf("%d%d",&from[i],&to[i]);if (from[i] > to[i]) swap(from[i],to[i]);mp[from[i]][to[i]] = i;vis[i] = false;}int Q;scanf("%d",&Q);for (int i = 0 ; i < Q ; i++){char op[20];scanf("%s",op);if(op[0] == 'q'){ask[i].op = 0;scanf("%d",&ask[i].u);}else{ask[i].op = 1;scanf("%d%d",&ask[i].u,&ask[i].v);if (ask[i].u > ask[i].v) swap(ask[i].u,ask[i].v);int tmp = mp[ask[i].u][ask[i].v];vis[tmp] = true;}}for (int i = 1 ; i <= M ; i++){if(!vis[i]) unionset(from[i],to[i]);}int tot = 0;for (int i = Q - 1 ; i >= 0 ; i--){if (ask[i].op == 0){int fu = Find(ask[i].u);if (val[fu] > p[ask[i].u]) ret[tot++] = pos[fu];else ret[tot++] = -1;}else{unionset(ask[i].u,ask[i].v);}}tot--;for (int i = tot ; i >= 0 ; i--) printf("%d\n",ret[i]);}return 0;
}

HDU 1272 小希的迷宫
一个无向图是不是树。注意坑点 第一：森林，第二：空树

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 100010;
int fa[MAXN];
int res[MAXN * 10];
int tot;
int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
int main()
{// freopen("sample.txt","r",stdin);int u,v;while (scanf("%d%d",&u,&v) != EOF){if (u == -1 && v == -1) break;if (u == 0 && v == 0){puts("Yes");continue;}for (int i = 0 ; i < MAXN ; i++) fa[i] = i;bool flag = false;int fu = Find(u);int fv = Find(v);if (fu != fv) fa[fv] = fu;tot = 0;res[tot++] = u;res[tot++] = v;while (scanf("%d%d",&u,&v) != EOF){if (u == 0 && v == 0) break;if (flag) continue;int fu = Find(u);int fv = Find(v);res[tot++] = u;res[tot++] = v;if (fu == fv) flag = true;else{fa[fv] = fu;}}sort(res,res + tot);tot = unique(res,res + tot) - res;// for (int i = 0 ; i < tot ; i++) printf("%d ",res[i]); puts("");int cnt = 0;for (int i = 0 ; i < tot ; i++){if (Find(res[i]) == res[i])cnt++;if (cnt >= 2){flag = true;break;}}if (flag) puts("No");else puts("Yes");}return 0;
}

POJ 1308 Is It A Tree?

有向图是不是树

连通后仅有一个点的入度为0，其他所有点的入度都为1 即为树

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define PI 3.1415926535897932626
using namespace std;
int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}
const int MAXN = 1000010;
int fa[MAXN];
int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
int deg[MAXN];
bool vis[MAXN];//这题用并查集判断连通，连通后有且仅有1个入度为0，其余入度为1，就是树了。//注意树为空的情况。int main()
{int u,v,kase = 1;while (scanf("%d%d",&u,&v) != EOF){if (u == -1 && v == -1) break;if (u == 0 && v == 0){printf("Case %d is a tree.\n",kase++);continue;}memset(vis,false,sizeof(vis));vis[u] = vis[v] = true;memset(deg,0,sizeof(deg));deg[v]++;for (int i = 0 ; i < MAXN ; i++) fa[i] = i;fa[v] = u;while (scanf("%d%d",&u,&v) != EOF){if (u == 0 && v == 0) break;int fu = Find(u);int fv = Find(v);if (fu != fv){fa[fv] = fu;}vis[u] = vis[v] = true;deg[v]++;}int num = 0,cnt0 = 0,cnt1 = 0;int pos;bool flag = false;for (int i = 1 ; i < MAXN ; i++){if (vis[i]){pos = i;break;}}int need = Find(pos);for (int i = pos ; i < MAXN ; i++){if (vis[i]){num++;if (deg[i] == 0) cnt0++;else if (deg[i] == 1) cnt1++;if (Find(i) != need){flag = true;break;}}}if (cnt0 == 1 && cnt1 + cnt0 == num && !flag) printf("Case %d is a tree.\n",kase++);else printf("Case %d is not a tree.\n",kase++);}return 0;
}

转载于:.html