TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3409
  • 题目
  • P3409【Codeforces #309 div1 C】Love Triangles
    限制 : 时间限制 : 10000 MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    很多时候都可以看到“三角恋”,例如Alice爱Bob,Charlie也爱Bob,但是Alice恨Charlie。你现在面对着包含n个人的世界,人编号依次是1到n,任意两个人要么相互爱着,要么相互恨着。
    你不喜欢“三角恋”(即A与B相互爱着,B与C相互爱着,但是A与C相互恨着),你也不喜欢“没有爱”(即A与B,B与C,A与C都相互恨着)。所以你希望世界上任意三个人要么“充满爱”(即A与B,B与C,A与C都相互爱着),或者“两情相悦”(即A与B相互爱着,A与C相互恨着,B与C也相互恨着)。
    你已经知道了m对人的爱恨关系,其他人的爱恨关系你暂时不知道。你希望这个世界就像你希望的那样,那么有多少种方案让这个世界想你希望的那样呢?答案可能很大,赶快mod 1000000007。

    输入格式

    第一行两个整数n,m,表示总人数和已知的关系数。
    接下来m行,每行三个数ai,bi,ci。如果ci=1则表示ai与bi相互爱着,如果ci=0则表示ai与bi相互恨着。
    任意一对人的关系只会被描述一次。

    输出格式

    输出一个整数,答案mod 1000000007的值。

    样例输入

    样例输入1:
    3 0

    样例输入2:
    4 4
    1 2 1
    2 3 1
    3 4 0
    4 1 0

    样例输入3:
    4 4
    1 2 1
    2 3 1
    3 4 0
    4 1 1

    样例输出

    样例输出1:
    4

    样例输出2:
    1

    样例输出3:
    0

    提示

    样例解释:
    第一组,可以“充满爱”(1种),也可以“两情相悦”(3种),共4种。
    第二组,不知道的关系中,1与3只能相互爱着,2与4只能相互恨着。

    数据范围:
    3<=n<=100000
    0<=m<=100000
    1<=ai,bi<=n,ai≠bi
    ci=0或1

    对于10%的数据,n,m<=10
    对于40%的数据,m<=10