首页 > 代码库 > 三角关系
三角关系
【题目描述】
假设每两个人之间只可能存在相互喜爱、相互憎恶两种关系，对于关系网中任意的三个人，如果他们之间的关系满足下面两个条件之一，那这个关系网就是良好的：
(1)这三个人两两之间相互喜爱；
(2)这三个人之间有两个人相互喜爱，另一个人与这两个人都相互憎恶；
现有一个关系网，询问如果随意填补缺失的信息，有多少种情况能够使得这个关系网是良好的，输出答案 mod 1000000007的值。
【输入描述】
第一行输入一个整数T，表示数据组数；
每组数据输入格式如下：
第一行输入两个整数n、m，表示关系网中的人数和已知的关系数目；
接下来m行，每行输入三个整数a、b、c，表示a和b之间的关系，如果c=0，则表示a和b相互憎恶，如果c=1，则表示a和b相互喜爱。
【输出描述】
共输出T行，每行包含一个数，表示答案。
【样例输入】
样例1：
1
3 0
样例2：
1
4 4
1 2 1
2 3 1
3 4 0
4 1 0
【样例输出】
样例1：
4
样例2：
1
【数据范围及提示】
对于第一组样例，四种情况为：
(1)每个人互相喜爱；
(2)1和2相互喜爱，1和3以及2和3相互憎恶；
(3)1和3相互喜爱，1和2以及3和2相互憎恶；
(4)2和3相互喜爱，1和2以及1和3相互憎恶；
对于30%的数据，T = 1，3 <= n <= 10，1 <= m <= 10；
对于100%的数据，T = 5，3 <= n <= 50000，1 <= m <= 200000。
三角关系
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。