这两天做了几道并查集的题目，hdu的联通工程啊more is better 啊，然后卡在hdu1829，带权的并查集，没搞懂，尝试写下来让思路清晰些。
并查集是一种维护不同集合，在此基础上实现快速判断，统计个数等等的算法。
基础的有find和join两个功能，其中join作用于接收新数据。
并查集应用场景的几个特点：
1.数据之间存在联系；
2.借由两个数据的联系，数据会被双向联通的结合成几个集合；
下面介绍下find和join的基本形式
const int maxn=1000;
int p[maxn];//用于储存数据的根
void init(int n)
{
for(int i=0;i<n;i++)
{
p[i]=i;
}
}
int find(int x)
{
int t=x;
while(p[t]!=t) t=p[t];
int i=x;
while(p[i]!=i)
{
int tem=p[i];
p[i]=t;
i=tem;
}
return t;
}
这种是将关系优化避免出现树变成一条路
还有一种如下
int find(int x)
{
if(p[x]==x)return x;
int tem=find(p[x]);
return tem;
}
这种用递归的方法算
join函数：
void join(int x,int y)
{
int f1=find(x),f2=find(y);
if(f1!=f2)
{
p[f1]=f2;
}}
知道了这些，一些水题就可以做了
接着是在这个基础上的变化，如统计集合个数，一开始的想法是维护完数据后for一遍，实际这里可以发现，在p[]数组中，作为根节点的数据p[i]==i的，没有必要通过链表结构特点去找根节点。接着处理掉这个for循环：
再看看现在的思路，是通过遍历一遍p[]数组，统计满足p[i]==i的个数，假设为a。如果所有数据没有联通，那么集合个数为n，a=n-（原本p[i]==i的点的p[i]改变的次数），即在join函数中每次寻找到两个数据的根数据进行合并时加一个计数器，然后用n减去。可以这样实现：
int ans=n;
void join(int x,int y)
{
int f1=find(x),f2=find(y);
if(f1!=f2)
{
p[f1]=f2;
ans--;
}
}
接着是找集合中元素个数的题1856，这个可以通过增加一个初始化为1的数组，每次合并同时对应合并，同时max取最大值
#include<iostream>
#include<string>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<map>
const int maxn = 10000005;
#pragma warning(disable:4996)
using namespace std;
// freopen("john.in", "r", stdin);
// freopen("john.out", "w", stdout);
int p[maxn];
int n[maxn];
void pre()
{
for (int i = 1;i < maxn;i++)
{
p[i] = i;
n[i] = 1;
}
}
int find(int x)
{
int r = x;
while (r != p[r])
{
r = p[r];
}
int i = x;
while (i != p[i])
{
int j = p[i];
p[i] = r;
i = j;
}
return r;
}
void join(int x, int y,int& ans)
{
int tem1 = find(x), tem2 = find(y);
if (tem1 != tem2)
{
p[tem1] = tem2;
n[tem2] += n[tem1];
ans = max(n[y], ans);
}
}
int main()
{
int t;
while (~scanf("%d", &t))
{
if (t == 0)puts("1");
else
{
int ans = 0;
pre();
while (t--)
{
int i, j;
scanf("%d%d", &i, &j);
join(i, j, ans);
}
printf("%d\n", ans);
}
}
}
还有一个应用是判断是否成环，如果join的两个数据p[]相同，则标记为成环，如1272这题，还要判断唯一性，可以用前面的方法，也可以通过图论中边数为定点数减一来判断
#include<iostream>
#include<string>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<map>
const int maxn = 100005;
#pragma warning(disable:4996)
using namespace std;
// freopen("john.in", "r", stdin);
// freopen("john.out", "w", stdout);
int p[maxn];
int flag;
bool s[maxn];
int find(int a)
{
while (a != p[a])
{
a = p[a];
}
return a;
}
void join(int a, int b)
{
int i = find(a), j = find(b);
if (i != j)
{
p[i] = p[j];
}
else flag = 0;
}
void pre()
{
for (int i = 1;i < maxn;i++)
{
p[i] = i;
s[i] = false;
}
}
int main()
{
int a, b;
while (cin >> a >> b)
{
if (a == -1 && b == -1)break;
if (a == 0 && b == 0)printf("Yes\n");
else
{
flag = 1;
pre();
s[a] = true;
s[b] = true;
join(a, b);
while (scanf("%d%d", &a, &b), (a || b))
{
s[a] = true;
s[b] = true;
join(a, b);
}
if (flag)
{
int cnt = 0;
for (int i = 1;i < maxn;i++)
{
if (s[i] && p[i] == i)
{
cnt++;
}
if (cnt > 1)
{
flag = 0;
break;
}
}
}
if (flag)printf("Yes\n");
else printf("No\n");
}
}
}
然后是1198这题，这题没有显示的给出数据间的关系，需要对数据进行处理，但并查集的部分没有什么新东西
#include<iostream>
#include<string>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<map>
const int maxn = 550;
#pragma warning(disable:4996)
using namespace std;
// freopen("john.in", "r", stdin);
// freopen("john.out", "w", stdout);
//上下左右分别为0123
int list[11] = { 10,9,6,5,12,3,11,14,7,13,15 };
char a[maxn][maxn];
int ans;
int n, m;
int p[maxn*maxn+1];
void pre(int n)
{
for (int i = 0;i < n;i++)
{
p[i] = i;
}
}
int find(int x)
{
int r = x;
while (r != p[r])
{
r = p[r];
}
return r;
}
void judge(int ai, int aj, int bi, int bj)
{
if (bi >= m || bj >= n)return;
bool flag = false;
int t1 = a[ai][aj] - 'A';
int t2 = a[bi][bj] - 'A';
if (ai == bi&&aj < bj)
{
if (((list[t1] ) & 1) && ((list[t2]>>1) & 1))flag = true;
}
else if (aj == bj&&ai < bi)
{
if(((list[t1] >> 2) & 1) && ((list[t2]>>3) & 1))flag = true;
}
if (flag)
{
int f1 = find(ai*n + aj), f2 = find(bi*n + bj);
if (f1 != f2)
{
p[f1] = f2;
ans--;
}
}
}
int main()
{
//freopen("in.txt", "r", stdin);
while (scanf("%d%d", &m, &n)!= EOF)
{
if (m == -1 || n == -1)break;
pre(m*n);
ans = n*m;
for (int i = 0;i < m;i++)
{
scanf("%s", a[i]);
}
for (int i = 0;i < m;i++)
{
for (int j = 0;j < n;j++)
{
judge(i, j, i, j + 1);
judge(i, j, i + 1, j);
}
}
printf("%d\n", ans);
}
}
然后是现在做的这题，关于带权并查集，还没有弄明白，1829，题意大概是选择动物，给出两个数据的性别相反，问是否出现前后矛盾的情况，上网看到一种解法，思路是开两个数组，每次接收数据，交换p[]中两个数据对应的值，如果有处理到两个数据的p[]相同，则错误。还有一种是带权并查集。做了一个晚上带权那种，还是有点没搞明白。
带权并查集多一个权值的数组，通过递归的find函数找到根节点。现在的问题是，每次找到根节点的过程和合并的过程，会让原本a->b->c的关系变成a->c,b->c每次更新后都要再次调整权值数组。网上的解释是把权值看成向量。例如sign[i]表示由i指向前一个节点的向量，那么改变后的指向由a->c，等于sign[a]+sign[p[a]]。
下面是代码：
#include<iostream>
#include<string>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#pragma warning(disable:4996)
using namespace std;
// freopen("john.in", "r", stdin);
// freopen("john.out", "w", stdout);
const int maxn = 2002;
int p[maxn];
int sign[maxn];
int find(int x)
{
if (p[x] == x) { return x; }
int tem = p[x];
p[x] = find(p[x]);
sign[x] = (sign[x] + sign[tem]) % 2;//用向量的思想来解释这个过程
return p[x];
}
void unit(int n)
{
for (int i = 1;i <= n;i++)
{
p[i] = i;
sign[i] = 0;
}
}
void join(int x, int y)
{
int f1 = find(x);
int f2 = find(y);
if (f1 != f2)
{
p[f1] = f2;
sign[f1] = (1 + sign[y] - sign[x]) % 2;
}
find(x);
}
int main()
{
freopen("in.txt", "r", stdin);
int t;
scanf("%d", &t);
int cnt = 1;
while (t--)
{
int n, m;
scanf("%d%d", &n, &m);
unit(n);
bool flag = true;
while (m--)
{
int i, j;
scanf("%d%d", &i, &j);
if(flag)join(i, j);
if (sign[i] == sign[j])
{
flag = false;
}
}
printf("Scenario #%d:\n", cnt++);
if (flag)printf("No suspicious bugs found!\n");
else printf("Suspicious bugs found!\n");
printf("\n");
}
}
现在还有个地方没有很清楚，就是在join函数中的sign[f1]的更新，为什么可以直接由sign[x]和sign[y]关系推到？
想通了！在find的过程中已经让x链接到根节点了
2017/4/26
今天学习了poj那道经典的食物链，有三个状态，看了结题报告，有两个细微不同的思路，一个是在状态数组sign里存0，1，2代表被吃，同类，吃的关系，另一种是在sign中存三种动物的种类，区别在更新sign数组的表达式上似乎有所不同。
通过这道题，一方面加深了关于向量关系的理解，另一方面是感觉数设的卡诺图化简作为二进制码逻辑关系的化简，这种思路在这种题里意外的有用【捂脸】
#include<iostream>
#include<string>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#pragma warning(disable:4996)
using namespace std;
// freopen("john.in", "r", stdin);
// freopen("john.out", "w", stdout);
const int maxn = 50002;
int p[maxn];
int sign[maxn];
void init(int n)
{
for (int i = 1;i <= n;i++)
{
p[i] = i;
sign[i] = 0;
}
}
int find(int x)
{
if (x == p[x])return x;
int tem = p[x];
p[x] = find(p[x]);
sign[x] = (sign[x] + sign[tem]) % 3;
return p[x];
}
bool join(int x, int y, int d)
{
int f1 = find(x), f2 = find(y);
if (f1 == f2)
{
if (d == 1 && sign[x] != sign[y])return false;
if (d == 2)
{
if (sign[x] == 2 && sign[y] != 1)return false;
if (sign[x] == 0 && sign[y] != 2)return false;
if (sign[x] == 1 && sign[y] != 0)return false;
}
return true;
}
p[f1] = f2;
if (d == 1)
{
sign[f1] = (sign[y] - sign[x] + 3) % 3;
}
if (d == 2)
{
sign[f1]=(sign[y] - sign[x] + 1 + 3) % 3;
}
find(x);//看看是否必要,可以ac，还是保留吧
return true;
}
int main()
{
// freopen("in.txt", "r", stdin);
int n, k;
scanf("%d%d", &n, &k);
init(n);
int ans = 0;
while (k--)
{
int d, x, y;
scanf("%d%d%d", &d, &x, &y);
if (x > n || y > n)
{
ans++;
continue;
}
if (x == y&&d==2)
{
ans++;
continue;
}
if (!join(x, y, d))ans++;//小心添加错的关系而对正确的关系造成破坏
//判断还是在函数中好，因为在这里会重复做过的事，找到find（x），（y）然后讨论sign[x]sign[y]的关系
}
printf("%d\n", ans);
}