首页 > 试题广场 >

人人都是好朋友

[编程题]人人都是好朋友

热度指数：2028 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛可乐作为三军统帅，是要时时刻刻关照着下属的。

现在牛可乐想要知道自己的手下之间的友好关系，所以他收集了 $n$ 张纸条，上面写着三个整数 $a_i,b_i,c_i$ ，表示如果 $c_i$ 为 $1$ ，表示手下 $a_i$ 和手下 $b_i$ 是朋友，反之则是敌人。

牛可乐想要知道这些信息有没有互相矛盾的地方，可是这个问题太难了，只好来问你了

如果 A 与 B 友好，B 又与 C 友好，那么 A 与 C 也是友好的。

如果两个人既是友好的又是不友好的则视为相互矛盾的。

牛可乐的手下有 1e9 个。

输入描述:

输入第一行给出一个正整数 $T$ ，表示测试案例的数量。

对于每个测试用例.第一行给出一个正整数 $n$ ，表示有 $n$ 个友好关系

接下来每 $n$ 行给出三个正整数 $a_i,b_i,c_i$ ，表示手下 $a_i$ 和手下 $b_i$ 之间的友好关系.

输出描述:

每组案例输出一行，若这些关系没有矛盾，输出 "YES”，否则输出 “NO”

示例1

输入

输出

YES
NO

备注:





对于每组样例，保证 
建议使用 scanf 读入

算法知识视频讲解

C++

Reisentyan

我们将使用拉马努金瞪眼法解决这一题

注意到，敌人的敌人就是朋友！

其实这一道题可以使用“种类并查集”的科技来进行实现

这里给出资料：浅谈并查集&种类并查集&带权并查集 - Eleven谦 - 博客园

简单的说，就是将 fa 数组的第 1 到 n 个位置标记为朋友，第 n+1 到 2n 个位置标记为敌人

似乎也可以不用这种办法，但是我想用种类并查集，于是就这样做了

注意到，并查集需要开 n 个元素，但是题目有 1e9 个不同的人，于是这里使用 unordered_map 进行优化即可！

注意到，代码要写成这样：

void solve() {
    int n = q_;
    unordered_map<int, int>fa;
    ffp(i, 1, (n + 1) << 1)fa[i] = i;

    auto find = [&](auto&& find, int a)->int {
        if (fa[a] == 0)fa[a] = a;
        return a == fa[a] ? a : fa[a] = find(find, fa[a]);
        };
    ffp(i, 1, n) {
        int a = q_;
        int b = q_;
        int c = q_;

        if (c == 1) {
            if (find(find, a + n) == find(find, b) || find(find, b + n) == find(find, a)) {
                //二者是敌人
                cout << "NO" << endl;
                return;
            }
            fa[find(find, a)] = find(find, b);
            fa[find(find, a + n)] = find(find, b + n);
        }
        else {
            if (find(find, a) == find(find, b)) {
                //二者是敌人
                cout << "NO" << endl;
                return;
            }
            fa[find(find, a)] = find(find, b + n);
            fa[find(find, b)] = find(find, a + n);
        }
    }
    cout << "YES" << endl;
}


int main() {
    int t = q_;
    while (t--) {
        solve();
    }

    return 0;
}


/*
⡀⠎⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣄⠃⠈⣶⡛⠿⠭⣉⠛⠿⡿⠛⠉⣀⣠⣤⣭⡏⠴⢀⣴⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣷⣱⣬⠛⠉⠀⠀⢠⠀⠀⠀⢀⣀⠀⠉⠿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠈⡿
⠀⠀⠀⠀⠀⠀⠀⢀⢿⣿⣿⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⡏⠀⠀⠀⠀⠈⠳⠀⠀⠀⠻⣿⣿⣿⣿⣿⣿⠋⠀⣇⠀⠀⠀⠀⠀⠀⠀⠀⠈
⠀⠀⠀⠀⠀⠀⠀⣸⠀⣿⣿⣿⣿⠟⠀⠀⠀⠂⠀⠀⢠⠀⠀⠀⠀⠀⠀⠀⠈⡀⠀⠀⠀⠻⣿⣿⣿⣿⣷⡀⠘
⠀⠀⠀⠀⠀⠀⠀⣧⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠙⣿⣿⣿⣿⣿⣄⣧
⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢧⠀⠀⠀⠀⠈⢿⣿⣿⣿⣿⣿⣆
⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⢂⠻⣿⣿⣿⣿⣿⣄
⠀⠀⠀⠀⠀⣿⣿⣿⣿⣹⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣇⠀⠀⠀⠀⠀⡄⠈⢿⣿⣿⣿⣿⣆
⠀⠀⠀⠀⣿⣿⣿⣿⠁⡇⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠀⠀⠀⠐⠸⠀⠀⠻⣿⣿⣿⣆⢦
⠀⠀⢠⣿⣿⣿⣿⠃⠀⠀⠀⠀⠀⠀⠀⣼⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡏⣧⠀⠀⠀⠀⠐⣇⠀⠀⠙⣿⣿⣿⡄⠙⣄
⠀⣴⣿⣿⣿⣿⠏⠀⢸⠀⠀⠀⠀⠀⠀⡿⢿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣃⣈⣦⠀⠀⠀⠀⢹⠀⠀⠀⠸⣿⣿⣿⠀⠀⠳⣀
⠋⣸⣿⣿⣿⡟⠀⠀⠀⡆⠀⠀⠀⠀⠀⡏⠙⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠀⢠⠀⠀⠀⢧⠀⠀⠀⠀⡇⠀⠀⠀⠘⣿⣿⣷⠀⠀⠘
⠀⣿⣿⣿⢩⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀⣀⠀⢱⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠂⢀⣴⣶⣿⣿⡀⠀⠀⢻⠀⠀⠀⠀⠹⣿⣿⡄
⢸⣿⣿⠃⠈⠀⠀⢸⠀⣿⣆⠀⠀⠀⠀⣿⣿⣿⠷⠘⡀⠀⠀⠀⠀⠀⠀⢠⢹⡀⠈⡿⠻⣿⣛⢿⣿⣷⡀⠈⠀⠀⠀⠀⠀⢻⣿⣿
⣿⣿⣿⠀⠀⠀⠀⢸⠀⡇⣼⣄⠀⠀⠀⢻⣿⡄⠑⠑⣿⡀⠀⠀⠀⢀⠀⠂⠇⠀⠀⠖⠛⢿⣿⣿⣌⢿⣿⣿⡆⠀⠀⠀⠀⠀⣿⣿⡀
⣿⣿⡇⠀⠀⠀⠀⢸⠀⣾⣿⣿⡷⠿⣷⣤⣿⣿⡄⠀⠀⠀⠑⠤⡀⠀⠃⠀⠀⠀⠀⣿⣶⣿⣿⣿⣿⣆⠙⣿⣧⠀⠀⠀⠀⠀⣿⣿⡇
⣿⣿⠁⠀⠀⠀⠀⠘⣾⣿⣿⠁⣴⣿⣿⣿⣿⣿⣇⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠸⡏⠙⣿⠉⠻⣿⠀⠀⣿⠀⠀⠀⣄⠀⣿⢸⣷
⣿⣿⡇⠀⠀⠀⠀⠀⣿⣿⠁⠀⣿⣿⠋⣿⠏⠙⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⢀⢻⠀⠀⢀⡟⢀⣿⣸⢃⠟
⣿⣿⣿⠀⡄⠀⠀⠀⠘⠻⡄⠀⢹⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡘⠀⢀⣿⠃⣿⣿⡗⠁
⣧⣿⣿⣧⢹⡀⠀⠀⠀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⣴⣿⣿⣾⣿⣿⣿
⢿⠘⣿⣿⣿⣿⣤⠀⠢⡀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣵⣿⣿⣿⣿⣿⣿⣿⣿⣷
⠀⠉⣿⣿⣿⡿⣿⠻⣷⣬⣓⣬⣄⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠉⠈⠈⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⠃⠼⢉⣿⣿⣿⣿⣿⣿⣿
⠀⠀⣿⣿⣿⣷⠀⠀⠀⠘⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⡏⠀⠀⢸⠀⢻⢿⣿⣿⡏⣿
⠀⢸⣿⣿⣿⣿⠀⠀⠀⠀⢻⣿⣿⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⣾⣿⣿⣿⣿⠀⠀⠀⢸⠀⠀⢸⣿⣿⠘⡀
⢦⡿⣿⣿⣿⢿⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣶⣶⣦⡄⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠘⡄⠀⠈⣿⣿⡄⠱
⣴⠛⣾⣿⣿⢸⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⡄⠀⠀⠀⠀⠀⠀⠀⣯⠛⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⣇⠀⠀⣿⣿⣿
⠿⠀⣿⣿⣿⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⠟⠰⡾⠃⠀⠀⠀⠀⠀⠀⠀⠙⡟⠀⢻⣿⣿⣿⣿⣿⡆⠀⠀⠀⠸⠀⠀⠸⣿⣿⣷
⠆⢳⣿⣿⡇⠀⠀⠀⠀⠀⠀⣿⣿⣿⠛⠿⠿⢿⡟⠀⠀⠉⠦⣀⡤⢶⠀⠖⠲⠶⠊⠀⠀⠀⢻⡛⠛⠛⣿⣿⠀⠀⠀⠀⠃⠀⠀⢿⣿⣿
*/

编辑于 2025-12-30 19:31:17 回复(2)

周康禧

并查集+离散化一下就行了，dsu随便写的，没按秩合并什么的，跑的1.6s，常数可能有点，离散化写的也有点丑陋了

struct DSU{
    int n;
    vector<int> f;
    void init(int _){
        n=_;
        f.resize(n+1);
        for(int i=1;i<=n;i++){
            f[i]=i;
        }
    }
    int find(int x){
        if(x==f[x])return x;
        else{
            return f[x]=find(f[x]);
        }
    }
    void merge(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y)return ;
        f[x]=y;
        return ;
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
};
int p(int x,vector<int> &v){
    int L=0,R=v.size(),pos=-1;
    while(L<=R){
        int mid=(L+R)>>1;
        if(v[mid]<=x){
            pos=mid;
            L=mid+1;
        }else{
            R=mid-1;
        }
    }return pos;
}
void solve(){
    int n;
    cin>>n;
    vector<pair<int,int>>q,r;
    vector<int> k;
    for(int i=1;i<=n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(c!=1){
            q.push_back({a,b});
        }else{
            r.push_back({a,b});
        }
        k.push_back(a);
        k.push_back(b);
    }
    sort(k.begin(),k.end());
    k.erase(unique(k.begin(),k.end()),k.end());
    unordered_map<int,int>f;
    DSU d;
    d.init(k.size()+1);
    for(int i=0;i<r.size();i++){
        int u,v;
        if(f.find(r[i].first)==f.end()){
            f[r[i].first]=p(r[i].first,k);
        }
        u=f[r[i].first];
        if(f.find(r[i].second)==f.end()){
            f[r[i].second]=p(r[i].second,k);
        }
        v=f[r[i].second];
        d.merge(u,v);
    }
    for(int i=0;i<q.size();i++){
        int u,v;
        if(f.find(q[i].first)==f.end()){
            f[q[i].first]=p(q[i].first,k);
        }
        u=f[q[i].first];
        if(f.find(q[i].second)==f.end()){
            f[q[i].second]=p(q[i].second,k);
        }
        v=f[q[i].second];
        if(d.same(u,v)){
            cout<<"NO"<<'\n';
            return ;
        }
    }cout<<"YES"<<'\n';
}

发表于 2025-12-30 23:13:11 回复(0)

Python3

驴主

时间限制 2 秒，不知道为什么我 3 秒也给过了。之前 Python 读大数据 TLE，让 AI 介绍了一种新方法：一次性全部读入分割。

本题使用冰茶几解决。

import sys

class IceCoffeeTable:
    def __init__(self) -> None:
        self.tea = {}
    def ice(self, a, b):
        ca = self.coffee(a)
        cb = self.coffee(b)
        self.tea[ca] = cb 
    def coffee(self, a):
        if a not in self.tea:
            self.tea[a] = a 
            return a
        if self.tea[a] == a:
            return a 
        self.tea[a] = self.coffee(self.tea[a])
        return self.tea[a]

    def table(self, a, b):
        return self.coffee(a) == self.coffee(b)

data = sys.stdin.read().split()
t = int(data[0])
i = 1
for _ in range(t):
    n = int(data[i])
    i += 1
    enemies = []
    ict = IceCoffeeTable()
    for _ in range(n):
        a, b, c = map(int, data[i: i + 3])
        i += 3
        if not c:
            enemies.append([a, b])
        else:
            ict.ice(a, b)
    for a, b in enemies:
        if ict.table(a, b):
            print('NO')
            break 
    else:
        print('YES')

# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⠶⠟⠛⠛⠛⠛⠷⡶⠶⠿⠛⠷⠶⣦⣤⡀
# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠶⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠶⣄
# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢶⡀
# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⠫⠒⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢄⠀⠀⠀⠀⠉⢷⡀
# ⠀⠀⠀⠀⠀⠀⣠⡾⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠒⡀⠀⠀⠀⠙⣦
# ⠀⠀⠀⠀⣠⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢆⠀⠀⠀⠘⣧
# ⠀⠀⠀⣴⠁⠀⢀⠤⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢣⠀⠀⠈⢿⡀
# ⠀⠀⡾⠀⣠⢾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡆⠀⠀⠀⠹⣆
# ⠀⢸⢁⠞⠀⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣿⠀⠀⠀⠀⠀⠀⢰⣿⠑⠢⣄⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠘⣆
# ⠀⠘⠃⠀⠀⡇⠀⠀⠀⠀⠀⠀⠀⠠⠋⢀⢏⢿⠀⠀⠀⠀⠀⢀⣿⣌⣆⠀⠀⣏⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠈⠀⠀⢄⠀⠀⢹⡀
# ⠀⠀⠀⠀⢀⡇⠀⠀⠀⠀⠀⠀⢠⠀⠀⡟⠟⢞⣇⠀⠀⠀⠀⢿⠟⠀⠙⣆⠀⢹⢦⡀⠀⠘⠀⠀⠀⠀⠀⠀⣄⠀⠀⠀⢳⡀⠀⣇
# ⠀⠀⠀⣤⠋⠀⠀⠀⠀⠀⠀⢀⡿⡄⢸⠙⠀⠀⠻⣆⢠⣄⠀⠀⣧⠀⠀⠀⠛⢦⣷⠙⢶⣄⠀⠀⠀⠀⠀⠀⠹⡀⠀⢠⣼⠻⡀⡟
# ⢀⣴⠟⠀⠀⠀⣀⠞⠀⠀⠀⣼⢋⠈⠻⠀⢀⣪⡶⠀⠛⠃⠉⠛⠻⣬⣑⣀⣀⣀⣤⣶⣷⣸⠀⠀⠀⠀⠠⠀⠀⠙⣄⠀⣿⠀⠛
# ⠀⠉⠛⠛⡿⠁⠀⠀⣄⠀⠀⣿⣿⣿⣿⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⣿⣿⣿⡿⠿⡿⠀⠀⠀⠀⠀⡾⠓⠶⠶⠋⠘⣦
# ⠀⠀⢀⠟⠀⠀⠀⣼⣿⣦⡀⠹⡀⠀⠙⠁⠀⠀⠒⠶⠒⠲⠤⠴⠀⠀⠀⠀⠁⠀⠀⠀⣾⠀⠀⠀⠀⠀⡾⠉⢷⣳⢄⠀⠀⠈⠳⣄
# ⠀⠀⡿⠀⠀⠀⣠⣿⣿⢿⣿⠉⠉⠎⢀⠀⡎⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠀⠃⢸⠀⣿⡤⣶⠁⠀⢠⣿⣿⠛⢀⣿⡇⡿⠶⣤⣤⣤⠟
# ⠀⠀⡇⠀⡴⢋⣼⠗⣉⢯⣿⣷⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡾⠀⣀⣾⠉⠉⠀⣠⣿⣿⣧⣿
# ⠀⠀⠹⠟⠀⣧⡴⣻⠃⣾⣿⣿⣋⠛⢶⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣛⣿⣿⣍⣴⣭⣿⡻⣿⣿⣿⣿⣞⣦
# ⠀⠀⠀⠀⠀⣾⣿⠃⢰⣿⠟⠐⣿⢏⣿⣿⣝⣿⣿⣿⠿⠶⠶⠶⠶⠶⠶⣿⠟⣩⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣷⣿⣦⣤
# ⠀⠀⠀⠀⠀⠠⣧⡀⣿⠁⢀⠋⢠⠋⠀⠙⠀⠉⠁⠀⠀⠀⠀⠀⠀⣴⣻⣿⣿⠦⣠⠛⠋⠁⣿⣿⠋⠻⣿⣿⣿⠉⠛⠿⠿⠛⠋
# ⠀⠀⠀⠀⠀⠀⠀⠀⣿⣾⢻⢠⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⢸⣿⡿⣵⠛⠀⠀⠀⠀⠁⠀⠀⠀⣿⠟
# ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠻⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣏⡟⡟
#

发表于 2025-12-30 02:52:30 回复(1)

提交观点

问题信息

难度：

3条回答 14收藏 89浏览

人人都是好朋友

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

相关试题