## 并查集小结

POJ-1182

POJ-1308

POJ-1611

POJ-1703

POJ-1988

POJ-2236

POJ-2492

POJ-2524

POJ-1456

POJ-1733

HDU-3038

POJ-1417

POJ-2912

baidu的题，AC了，不过有一些乱，一时间【【【再看看】】】

ZOJ-3261   NUAA-1087

POJ-1861  POJ-2560

Kruskal并查集

## 名叫并查集

那题是上大器晚成题（Find them and Catch
them卡塔尔的难度越来越高的本子，倘令你没做的话提出先做充足，用并查集来解，分成二种情景，因为要询问关系，直接查不能够查，于是以根节点作为中继点，每种节点做二个标志表示与根节点的涉及，0象征与根同类，1象征吃根，2代表被根吃，也不得不是这三个数，不可能使-1,1，0或其余什么的，因为那样不可能转正。

# 别的那个文章很好：

四个操作代码：
int Find(int x)
{
if (tree[x].parent != x)
{
tree[x].parent = Find(tree[x].parent);
}
return tree[x].parent;
}

void Merge(int a, int b, int p, int
q, int d)
{
if (tree[q].depth > tree[p].depth) tree[p].parent =
q;
else
{
tree[q].parent = p;
if (tree[p].depth == tree[q].depth)
tree[p].depth++;
}
}

POJ 1182 食物链
http://acm.pku.edu.cn/JudgeOnline/problem?id=1182

B,
C三类，在统不平时改进根结点的花色，其余点相应改动偏移量。但这种办法公式很难推，非常是偏移量十分轻巧计算错误。

b子树的根结点。
1. 如果p != q，表明a,
b权且并未有关联，那么关于她们的判定都以不利的，然后合併那七个子树。这里是尤为重要，如何统风度翩翩七个子树使得合併后的新树能保险科学吧？这里大家规定只好p合併到q(刚才说过了，启迪式归拢的优化职能并不那么显著，要是大家用启迪式合併，就要推出多个姿态，而以此推式子是件相比较累的活…所以日常我们都规定叁个子树合到另二个子树)。那么合并后，p的relation料定要退换，那么改成多少吧？这里的方法正是找规律，列出一些也许的事态，就大致能临蓐式子了。这里式子为
: tree[p].relation = (tree[b].relation – tree[a].relation + 2 + d)
% 3; 这里的d为判定语句中a,
b的涉及。还应该有个难题，大家是还是不是要求遍历整个a子树并立异每种结点的事态呢？答案是无需的，因为大家得以在Find()函数微微校正，即结点x世袭它的老爹(注意是前阿爹，因为路线压缩后阿爹就能转移)，即它会再而三到p结点的退换，所以大家无需种种都遍历过去翻新。
2. 借使p = q，表达a,
b早前曾经有提到了。那么我们就判定语句是或不是是对的，雷同找规律推出式子。即if
( (tree[b].relation + d + 2) % 3 != tree[a].relation ),

3.

主旨的三个函数为：
int Find(int x)
{
int temp_p;
if (tree[x].parent != x)
{
//

temp_p = tree[x].parent;
tree[x].parent = Find(tree[x].parent);
//
x与根结点的关联更新(因为根结点变了)，那个时候的temp_p为它原来子树的根结点.
tree[x].relation = (tree[x].relation +
tree[temp_p].relation) % 3;
}
return tree[x].parent;
}

void Merge(int a, int b, int p, int
q, int d)
{
// 公式是找规律推出去的.
tree[p].parent = q; // 这里的下标相近，都是tree[p].
tree[p].relation = (tree[b].relation – tree[a].relation

• 2 + d) % 3;
}

1308 1611 1703 1988 2236 2492 2524。

下边来上课几道微微升高点的标题:
POJ 1456 Supermarket
http://acm.pku.edu.cn/JudgeOnline/problem?id=1456

Find(b[i]) –
1)就可以。相似这里大家显然只可以左臂的子树合并到左侧的子树(想一想怎么～～)。

POJ 1733 Parity game

http://acm.pku.edu.cn/JudgeOnline/problem?id=1733
那题雷同用临近食品链的考虑。

b，大家把b++，假使他们在二个成团内，那么区间[a,
b]里1的个数也正是b.relation ^
a.relation，判别对错就可以。要是不在三个聚焦内，合併集结(这里大家明确根结点小的子树归拢根结点大的，所以要依照分裂景观推式子)，修改子树的根结点的场所，子树的其他结点状态通过Find()函数来更新。

hdu 3038 How Many Answers Are Wrong

http://acm.hdu.edu.cn/showproblem.php?pid=3038

100]里面，那么后生可畏旦a,
b不在三个子树内，大家就联合，但在统一此前还要推断合併后会不会使得区间的和非法，如果会注明该联合是不法的，那么就不合併，相像以为该句话是荒谬的。

POJ 1417 True Liars(难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1417
并查集 + DP(或搜索)。

现在的主题材料转变为，有n个集结，各样集合都有a,
b连个数字，今后要求n个集合中各跳出二个数(a或许b)，使得他们之和格外n1(说心声的总人口)。而这一个用dp可以很好的解决，用f[i][j]意味着到第i个聚众和为j个的场地数，大家还用过pre[i][j]记录当前选的是a依然b，用于末端推断状态。方程为f[i][j]
= f[i – 1][j – a] + f[i – 1][j – b], j >= a, j >=
b。假若最终f[n][n1] == 1表明是独一无二的境况，输出该地方，不然输出
“no”(多解算no)
注意点 :
1. 那题的m, n1, n2皆有十分大可能率现身0，能够破例管理，也得以一齐管理。
2.

1时，大家都让它等于2就能够。

POJ 2912 Rochambeau(难)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2912
Baidu Star 二零零五Preliminary的标题，以为出的很好，在并查集标题中毕竟较难的了。其实这题跟食物链完全三个磨子，相近三类食品，相符的相互制约关系。所以食品链代码拿过来改都无需改。但那题有个judge，他能够当作意手势。于是我们的做法是，枚举各样娃娃为judge，判断她为judge时在第几句话出错err[i](即到第几句话能看清该孩子不是judge)。
1.

2.

3. 多于1个小孩是judge时未有找到出错的语句，就是Can not
determine。     ZOJ 3261 Connections in Galaxy War         http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3563

nuaa 1087 联通or不连通

http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1087

czyuan原创，转发请注脚出处。

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

N
Y
N
Y

# 花色并查集报告

POJ-1703    POJ-1182
POJ-2492都以这种题。

——————————————————————————

poj 1182

http://acm.pku.edu.cn/JudgeOnline/problem?id=1182

#include <iostream>
using namespace std;
struct point{
int parent;
int kind;
} ufind;
void init(int n);
int find(int index);
void unions(int rootx, int rooty, int x, int y, int dkind);
int main()
{
int n,k,count=0,d,x,y;
scanf(“%d%d”,&n,&k);

init(n);
while(k–)
{
scanf(“%d%d%d”,&d,&x,&y);
if(x>n || y>n)
count++;
else if(d==2 && x==y)
count++;
else
{
int rx=find(x);
int ry=find(y);
if(rx!=ry)
unions(rx,ry,x,y,d-1);
else
{
if(d==1 && ufind[x].kind!=ufind[y].kind)
count++;
if(d==2 && (ufind[x].kind-ufind[y].kind+3)%3!=1)
count++;
}
}
}
printf(“%d\n”,count);

return 0;
}
void init(int n)
{
for(int i=1;i<=n;i++)
{
ufind[i].parent=i;
ufind[i].kind=0;
}
}
int find(int index)
{
int temp;
if(index==ufind[index].parent)
return index;
temp=ufind[index].parent;
ufind[index].parent=find(ufind[index].parent);
ufind[index].kind=(ufind[temp].kind+ufind[index].kind)%3;
return ufind[index].parent;
}
void unions(int rootx, int rooty, int x, int y, int dkind)
{
ufind[rooty].parent=rootx;
ufind[rooty].kind=(-dkind+(ufind[x].kind-ufind[y].kind)+3)%3;
}

1.这里并查集(ufind)的四个同类集合寄存的是基于本来就有科学揣测有关系的点，这里的关系满含了吃，被吃，同类四个关系；
2.涉及是透过kind来代表的，其值为0，1，2，即使ufind.kind==ufind.kind，说明1，2点同类；如果
(ufind.kind-ufind.kind+3)%3==1，说明1吃2；
3.并查集是按索引部分集体起来的，即同生机勃勃类的点都有一同的根结点；
4.并查集涵Guy始化(init)，查找(find)，归并(unions)操作，在那之中有好些个关键点，笔者都在代码中用革命标识。上边逐条分解这个关键点：
(1)ufind[i].kind=0;种类开头化为0，那些近乎很简短，但它事实上保险了并查聚焦每一个类的根结点的kind属性为0，那是前面三个关键式推导的根基；
(2)ufind[rooty].kind=(-dkind+(ufind[x].kind-ufind[y].kind)+3)%3;这句出现在联合操作里面，这里要分解的是，在统一早前种种类的群集中享有父节点为根结点的点甚至根结点，它们之间的涉及都以没有错的，归可想而知后只保障了归拢前原多少个聚众的根结点之间的关系精确，即在新的联合后的聚聚焦仍保管全数父节点为根结点的点以致根结点之间的涉及准确。那样大家在做联合操作时，是经过多个事关推到出预归并的四个根结点(rootx,rooty)之间的没有错关系的：x和rootx的涉嫌，y和rooty的系，x和y的涉及。那正是其大器晚成姿势的原因，此中使用了前边说过的rootx和rooty为0的结论。
(3)ufind[index].kind=(ufind[temp].kind+ufind[index].kind)%3;这句出未来物色操作里，成效是将待查找的点到它的根结点所通过的全部一点点举行三个操作，一是把它们的父节点都设为根结点；二是根据从离根结点以来的不得了点起来到待查找的点的逐大器晚成把它们与根结点的涉及设置成正确值(原先有相当大希望是荒谬的，因为联合操作只保障了全体父节点为根结点的点以致根结点之间的涉嫌不错)。那样之后那些集结中依旧保险了富有父节点为根结点的点以至根结点之间的关联不错，何况待观看的点的父节点为根结点。上面来讲明下为何要遵纪守法从离根结点以来的丰裕点开端到待查找的点的逐豆蔻梢头，这也是以此姿势为啥如此写的从头至尾的经过：假如1为根结点，Kind为0，其子节点为2，kind为k2，2的子节点为3，kind为k3；因为老是合并只会集根结点，所以3在1，2归拢前的根结点一定是2，即若2的kind为0，则3和2的关系就不易了，但归拢时2的kind加上了k2，保险了1与2的涉嫌不错而并未更新k3(这是因为并查集集结中不能够从父节点找到子结点，所以等到寻找时，要用到该点时再改善也不迟)，所以那时候风流罗曼蒂克旦将(k2+k3)%3就足以得到准确的以1为规范的3的kind。接下来，k3的kind更改了，k4能够以k3为根底同样通过此措施更改，直到要查的结点，并把它们整个高悬根结点上。 😉 XBWer

0

0

(请你对文章做出争论)

«博主前豆蔻年华篇：怎么是Windows能干而Linux干不了的事体？

posted @ 2012-08-04 21:12
XBWer 阅读(0) 评论(0) ### 初始化

``````    father[i]=i;
``````

``````    for(int i=1;i<=n;/*n即n个元素*/i++)
father[i]=i;
``````

### 函数

``````int getfather(int x)//找x的根结点
{//这其实是一个递归函数
if(father[x]==x)//边界条件，如果x的根结点就是x（也就是说它没有更上边的祖宗了）
return x;//就会返回x的值
else
{
father[x]=getfather(father[x]); //不然的话就会一级一级找上去（先找到它爸爸，在找到它爸爸的爸爸，再找到它爸爸的爸爸的爸爸。。。。。）
}
return father[x];
}
``````
``````在findset时要记得根据该节点与其父节点的关系和父节点与爷爷节点的关系来推出该节点与他的爷爷节点的关系，做到实时更新（因为合并会使他的标记变化）。

1.如果断言为a和b同类
{
1.如果在同一集合，判断ca[a]是否等于ca[b]
2.不在同一集合则合并，此时
ca[x] = (-ca[a] + ca[b] + 3)%3;   //加3是为了防止负数
因为图示：
}
2.如果断言为a吃b
{
1.如果在一个集合，判断是否有a吃b的关系
if((ca[a] + 2)%3 =?= ca[b])..
怎么来的自己可以推导一下
2.如果不在，合并
ca[x] = (-ca[a] + 1 + ca[b] + 3)%3;  //加3是为了防止负数
}
``````

### 读入

``````for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&z[i],&x[i],&y[i]);
z1[i]=getfather(x[i]);//z1数组用于存储每一个x[i]的根结点
z2[i]=getfather(y[i]);//z2数组用于存储每一个y[i]的根结点
}
``````

### 并集

``````if(z[i]==1)
{
if (z1[i]!=z2[i])
Union(z1[i],z2[i]);
}
``````

``````void Union(int xx,int yy)
{
int f1=getfather(xx);//f1就是 xx的根结点
int f2=getfather(yy);//f2就是yy的根结点
father[f1]=f2;//让xx的根结点成为yy的根结点（上面有解释）
return;
}
`````` ### 查集

``````if(z[i]==2)
{
if(getfather(x[i])==getfather(y[i]))//如果 x[i]的根结点就是y[i]的根结点
{
cout<<"Y"<<endl;//就输出y
}
else
{
cout<<"N"<<endl;//不然就输出 n
}
}
``````

``````#include<iostream>
#include<cstdio>
using namespace std;
int n,m,father;
int z,y,x;
int getfather(int x)
{
if(father[x]==x)
return x;
else
{
father[x]=getfather(father[x]);
}
return father[x];
}
void Union(int xx,int yy)
{
int f1=getfather(xx);
int f2=getfather(yy);
father[f1]=f2;
return;
}
int main()
{
int z1,z2;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
father[i]=i;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&z[i],&x[i],&y[i]);
z1[i]=getfather(x[i]);
z2[i]=getfather(y[i]);
}
for(int i=1;i<=m;i++)
{
if(z[i]==1)
{
if (z1[i]!=z2[i])
Union(z1[i],z2[i]);
}
if(z[i]==2)
{
if(getfather(x[i])==getfather(y[i]))
{
cout<<"Y"<<endl;
}
else
{
cout<<"N"<<endl;
}
}
}
return 0;
}
``````

tks ``````#include <iostream>
#include <cstdio>
using namespace std;
#define N 50100
int fa[N],ca[N];

void makeset(int n)
{
for(int i=1;i<=n;i++)
{
fa[i] = i;
ca[i] = 0;   // 0:同类  1:吃  2:被吃
}
}

int findset(int x)
{
if(x != fa[x])
{
int tmp = fa[x];
fa[x] = findset(fa[x]);
ca[x] = (ca[x] + ca[tmp])%3;
}
return fa[x];
}

int unionset(int op,int a,int b)
{
int x = findset(a);
int y = findset(b);
if(op == 1)  //a与b是同类关系
{
if(x == y)  //如果已经在一个集合里面了，则判断这句话的真假即可
{
if(ca[a] == ca[b])
{
return 0;   //假话增量为0，说明是真话
}
else
return 1;   //假话增量为1，说明是假话
}
else   //还不在一个集合中，合并两个集合
{
fa[x] = y;
ca[x] = (-ca[a] + ca[b] + 3)%3;
}
}
else     //op = 2 ,a吃b的关系
{
if(x == y)   //在一个集合中，判断是否正确
{
if((ca[a] + 2)%3 == ca[b])  //这样才能形成 a吃b吃gen吃a 即形成a 吃 b 的关系
{
return 0;  //假话增量为0
}
else
return 1;
}
else    //不在一个集合中，合并
{
fa[x] = y;
ca[x] = (-ca[a] + 4 + ca[b])%3;
}
}
return 0;   //不处理的返回值
}

int main()
{
int n,k,cnt,i;
int op,a,b;
scanf("%d%d",&n,&k);
cnt = 0;
makeset(n);
for(i=0;i<k;i++)
{
scanf("%d%d%d",&op,&a,&b);
if(a > n || b > n)
cnt++;
else if(op == 2 && a == b)
cnt++;
else
cnt += unionset(op,a,b);
}
cout<<cnt<<endl;
return 0;
}
``````

View Code
{"ft_lang_label":"__label__zh","ft_lang_prob":0.638036,"math_prob":0.9959067,"size":12551,"snap":"2020-24-2020-29","text_gpt3_token_len":9531,"char_repetition_ratio":0.10002391,"word_repetition_ratio":0.07360673,"special_character_ratio":0.2977452,"punctuation_ratio":0.17132552,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.98364437,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12],"im_url_duplicate_count":[null,null,null,1,null,3,null,1,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-06-01T13:39:29Z\",\"WARC-Record-ID\":\"<urn:uuid:8bd39cb7-f57c-4eb1-a81a-e0df54128755>\",\"Content-Length\":\"45123\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:52e886be-a1a2-4d79-9f07-565428e63fed>\",\"WARC-Concurrent-To\":\"<urn:uuid:ca00f253-43bc-435b-a09c-9c2b8bccd73b>\",\"WARC-IP-Address\":\"154.218.195.14\",\"WARC-Target-URI\":\"https://www.ctfyqd.com/archives/5246.html\",\"WARC-Payload-Digest\":\"sha1:MYF53KBZBNTZX6FHYL5NJXHKVP3QVWDH\",\"WARC-Block-Digest\":\"sha1:NVBWELIVFLZOJWJZWJTS554DJOHVCEZM\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-24/CC-MAIN-2020-24_segments_1590347417746.33_warc_CC-MAIN-20200601113849-20200601143849-00522.warc.gz\"}"}