算法训练营:等式
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法训练营:等式,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2307字,纯文字阅读大概需要4分钟。
内容图文
题目:
描述
有n个变量和m个“相等”或“不相等”的约束条件,请你判定是否存在一种赋值方案满足所有m个约束条件。
输入
第一行一个整数T,表示数据组数。
接下来会有T组数据,对于每组数据:
第一行是两个整数n,m,表示变量个数和约束条件的个数。
接下来m行,每行三个整数a,b,e,表示第a个变量和第b个变量的关系:
- 若e=0则表示第a个变量不等于第b个变量;
- 若e=1则表示第a个变量等于第b个变量
输出
输出T行,第i行表示第i组数据的答案。若第i组数据存在一种方案则输出"Yes";否则输出"No"(不包括引号)。
输出样例1
2 5 5 1 2 1 2 3 1 3 4 1 1 4 1 2 5 0 3 3 1 2 1 2 3 1 1 3 0
输出样例1
Yes No
样例1解释
一共有2组数据。
对于第一组数据,有5个约束:
- 变量1=变量2
- 变量2=变量3
- 变量3=变量4
- 变量1=变量4
- 变量2≠变量5
显然我们可以令:
- 变量1=变量2=变量3=变量4=任意一个数值
- 变量5=任意一个和变量2不同的数值
故第一组数据输出"Yes"。 对于第二组数据,有3个约束:
- 变量1=变量2
- 变量2=变量3
- 变量1≠变量3
由前两个约束可推出变量1=变量3,但第三个约束表明变量1≠变量3,矛盾。
故第二组数据输出"No"。
限制
对于10%的数据,n,m ≤ 5,T ≤ 5;
对于50%的数据,n,m ≤ 1000,T ≤ 10;
对于100%的数据,1 ≤ n,m ≤ 500000,1 ≤ a,b ≤ n,T ≤ 100。
保证所有数据的n总和与m总和不超过500000。
时间:2 sec
空间:256 MB
提示
代码实现
#include <iostream> #include <vector> usingnamespace std; // ================= 代码实现开始 =================constint N = 300005 ; //Father : 每个节点的父亲节点 //Rank : 节点的秩int Father[N] , Rank[N] ; //查找节点x所有集合的根 // x : 节点x 返回值 :根int find( int x ){ return Father[x] == x ? x : Father[x] = find( Father[x] ) ; } // 给定n个变量以及m个约束,判定是否能找出一种赋值方案满足这m个约束条件 // n:变量的个数 // m:约束条件的个数 // A:大小为m的数组,表示m条约束中的a // B:大小为m的数组,表示m条约束中的b // E:大小为m的数组,表示m条约束中的e // 返回值:若能找出一种方案,返回"Yes";否则返回"No"(不包括引号)。string getAnswer(int n, int m, vector<int> A, vector<int> B, vector<int> E) { //初始化for( int i = 1 ; i <= n ; i++ ) { Father[i] = i ; Rank[i] = 0 ; //各个节点的秩起初都是0 } // 将 e = 1 都放到 e = 0 前面int cnt = 0 ; for( int i = 0 ; i < m ; i++ ) { if( E[i] == 1 ) { swap( E[i] , E[cnt] ) ; swap( A[i] , A[cnt] ) ; swap( B[i] , B[cnt] ) ; cnt++ ; } } for( int i =0 ; i< m ; i++ ) { int setA = find( A[i] ) ; //找到A[i]所有集合的根int setB = find( B[i] ) ; //找到B[i]所有集合的根if( E[i] == 0 ) { if( setA == setB ) return"No" ; } else{ if( setA != setB ) { if( Rank[setA] > Rank[setB] ) swap( setA , setB ) ; //RankB 的父节点更高 Father[setA] = setB ; if( Rank[setA] == Rank[setB] ) Rank[setB] ++ ; } } } return"Yes"; } // ================= 代码实现结束 =================int main() { int T; for (scanf("%d", &T); T--; ) { int n, m; scanf("%d%d", &n, &m); vector<int> A, B, E; for (int i = 0; i < m; ++i) { int a, b, e; scanf("%d%d%d", &a, &b, &e); A.push_back(a); B.push_back(b); E.push_back(e); } printf("%s\n", getAnswer(n, m, A, B, E).c_str()); } return0; }
原文:https://www.cnblogs.com/syyyyy/p/10346975.html
内容总结
以上是互联网集市为您收集整理的算法训练营:等式全部内容,希望文章能够帮你解决算法训练营:等式所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。