我要招人

去企业版

首页 > 试题广场 >

人人都是好朋友

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

热度指数：2037 时间限制：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 读入

算法知识视频讲解

白色L号谢谢

发表于 2020-04-18 22:53:47

考点:并查集，离散化。这题题意很明确，做法也很明确。先对友好的弄一个并查集，最后再查询敌人是否为友好关系。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long 展开全文

BaiJay

发表于 2025-12-30 09:19:52

由于节点数量太多，所以考虑使用哈希表优化的并查集，另外合并不使用递归防止深度过大发生段错误；由于朋友之间具有传递性，所以可以把所有的朋友看作是一个集合，从这里可以想到使用并查集 #include <bits/stdc++.h> #define int long long usin 展开全文

QQQQwQQQQ

发表于 2020-04-19 15:15:15

本题考查了并查集+离散化题干中“如果 A 与 B 友好，B 又与 C 友好，那么 A 与 C 也是友好的”---->并查集关于并查集可看看CSDN：https://blog.csdn.net/qq_41593380/article/details/81146850“手下1e9个”说明直接使用h 展开全文

Meul

发表于 2020-04-19 18:37:53

Question 张纸条，上面写着三个整数。若表示和为朋友。否则表示其为敌人。朋友的朋友也是朋友，问是否有矛盾的情况？ Solution 离散化并查集矛盾的情况为既是朋友又是敌人，很容易想到利用并查集去处理这里的关系。"牛可乐的手下有 1e9 个"这句话是告诉我们直接开数组是要MLE的，展开全文

smartiphone

发表于 2025-12-30 11:08:26

#include<bits/stdc++.h> #define endl '\n' using namespace std; class dsu { vector<int> par; vector<int> rank; public: 展开全文

quchen666

发表于 2025-12-30 13:14:55

#include <bits/stdc++.h> using namespace std; const int N =5e6+10; int fa[N]; int n; int cnt; int ai[N],bi[N],ci[N]; void init() { for(int 展开全文

duang0925

发表于 2025-12-30 18:00:23

#include <bits/stdc++.h> using namespace std; using ll = long long; // const ll len = 1e9; struct E { int a, b, c; E() {} E(int _a, 展开全文

怎么不AC啊

发表于 2025-12-30 01:19:38

#include <cassert> #include <iostream> #include <unordered_map> #include <vector> #include <bits/stdc++.h> using namespa 展开全文

ddhw111

发表于 2025-12-30 02:05:18

#include<bits/stdc++.h> #define endl "\n" #define int long long using namespace std; struct node { int u, v, w; bool operator 展开全文

ATRI_execution

发表于 2025-12-30 12:37:06

import sys """ 并查集的完整结构，由于python该死的性能开销问题，只能抽取主干直接在函数内实现了（rank和排序部分也可以不管，反正不是多次处理加上极端情况的话是大树接小树还是小树接大树区别没那么大） class UnionFind: def 展开全文

问题信息

难度：

3条回答 15收藏 303浏览

人人都是好朋友

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

相关试题