华为od机试真题（华为OD机试 – 无向图染色（Java & JS & Python））

题目描述

给一个无向图染色    
    
    
，可以填红黑两种颜色     


     


     


   ，必须保证相邻两个节点不能同时为红色




 




 




 

，输出有多少种不同的染色方案？

输入描述

第一行输入M(图中节点数) N(边数)

后续N行格式为：V1 V2表示一个V1到V2的边    
    
    
。

数据范围：1 <= M <= 15,0 <= N <= M * 3
   

   

   

，不能保证所有节点都是连通的     


     


     


   。

输出描述

输出一个数字表示染色方案的个数




 




 




 

。

用例

输入 4 4

1 2

2 4

3 4

1 3 输出 7 说明

4个节点     

     

     

  ，4条边 




  




  




  
，1号节点和2号节点相连

  


  


  


，

2号节点和4号节点相连     
     
     
 ，3号节点和4号节点相连  




   




   




   ，

1号节点和3号节点相连


 



 



 



，

若想必须保证相邻两个节点不能同时为红色               ，总共7种方案
   

   

   

。