十五月明

用户名：dotcpp0605328

访问量：5427

签　名：

等　　级
排　　名	319
经　　验	5465
参赛次数	0
文章发表	87
年　　龄	18
在职情况	学生
学　　校	曲阜师范大学
专　　业	人工智能

　　自我简介：

Easy

TA的其他文章

1072: 汽水瓶
浏览：64

1074: 数字整除(拿50分就够了)
浏览：53

1075: 台球碰撞（绝对牛逼！！！）
浏览：91

你可能喜欢

团伙(group) 并查集

　　作者: 十五月明　　　　发表时间：2024-10-20 20:08:44 浏览：57　|　评论：0　

原题链接：团伙(group)

#include<bits/stdc++.h>
    using namespace std;
    int n,m;
    int o,p,q;
    int father[1001];
    int e[1001];
    int res=0;
    
    int find(int x){
        if(father[x]!=x){
            x=find(father[x]);
        }
        return father[x];
    }
    void initial(){
        for(int i=1;i<=n;i++){
            father[i]=i;
            e[i]=0;
        }
    }
    void Union(int a,int b){
        int x=find(father[a]);
        int y=find(father[b]);
        if(x!=y){
            father[x]=y;
        }
    }
    int main()
    {
        cin>>n>>m;
        initial();
        for(int i=1;i<=m;i++){
            cin>>o>>p>>q;
            if(o==0) Union(p,q);
            else{
    			if(e[p]==0) e[p]=find(q);
    			else Union(q,e[p]);
    			if(e[q]==0) e[q]=find(p);
    			else Union(p,e[q]);
    		}
        }
        for(int i=1;i<=n;i++){
            if(father[i]==i) res++;
        }
        cout<<res;
        return 0;
    }
最基础的并查集是给出关系直接合并，这道题呢稍微多了一些条件，就是敌人的敌人也是自己的朋友，所以在合并的时候多了几步操作。
首先，要充分理解题目。 “敌人的敌人就是朋友”可以这么理解：如果一个人有两个或更多敌人，这些敌人就应该被合并。
代码中的e数组就是记录了每个人的第一个敌人，再遇到敌人时就把这两个敌人合并。
Friend合并，e记录，再把下一个e和记录的e合并。因为敌人的敌人是朋友。比如1 1 2, 1 2 3 记录e[1] = 2, e[2] = 1，现在到了1 2 3， e[2]有了，那么把1,3合并，然后记录e[3] = 2。由于敌人的敌人已经合并，那么这时的1或者3都是2的敌人，取一个代表就行，下次再碰到2和某个人是敌人，把他和1合并或把它和3合并是一样的。连通块在合并的时候统计就可以了。

于是就有了下面这部分的代码：
if(e[p]==0) e[p]=find(q);
         	else Union(q,e[p]);
            if(e[q]==0) e[q]=find(p);
            else Union(p,e[q]);
*这段代码是在处理o==1的情况，即不是合并操作，而是某种形式的边操作。这里的逻辑似乎是：
如果e[p]为0，说明节点p之前没有与其他节点通过边连接，那么就把p的边指向q所在的集合的根节点。
如果e[p]不为0，说明p已经与某个节点通过边连接，那么就把q和e[p]所在的集合合并。
类似地，对于节点q，如果e[q]为0，就把q的边指向p所在的集合的根节点。
如果e[q]不为0，就把p和e[q]所在的集合合并。*

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

十五月明

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

Tom数（C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

WU-判定字符位置（C++代码）

团伙(group) 并查集

评论区

精彩推荐

WU-整除问题（C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

字符逆序（C语言代码）

字符逆序（C语言代码）

大家好，我是验题君

1128题解（返回值为数组的情况）

A+B for Input-Output Practice (I) （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言训练-百钱百鸡问题（C语言代码）

小九九（C语言代码）

十五月明

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

Tom数 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

WU-判定字符位置 （C++代码）

团伙(group) 并查集

评论区

精彩推荐

WU-整除问题 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

字符逆序 （C语言代码）

字符逆序 （C语言代码）

大家好，我是验题君

1128题解（返回值为数组的情况）

A+B for Input-Output Practice (I) （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言训练-百钱百鸡问题 （C语言代码）

小九九 （C语言代码）

Tom数（C语言代码）

WU-判定字符位置（C++代码）

　　评论区

WU-整除问题（C++代码）

字符逆序（C语言代码）

字符逆序（C语言代码）

C语言训练-百钱百鸡问题（C语言代码）

小九九（C语言代码）