题目描述

给一个无向图染色，可以填红黑两种颜色，必须保证相邻两个节点不能同时为红色，输出有多少种不同的染色方案?

输入描述

第—行输入M(图中节点数)N(边数)
后续N行格式为:V1V2表示一个V1到V2的边。
数据范围: 1<=M<= 15,0 <=N<=M *3，不能保证所有节点都是连通的。

输出描述

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

用例

输入

4 4
2 4
3 4
1 3
1 2

输出

7

说明

4个节点，4条边，1号节点和2号节点相连，2号节点和4号节点相连，3号节点和4号节点相连，
1号节点和3号节点相连，若想必须保证相邻两个节点不能同时为红色，总共7种方案。

思路

对每个节点可能的染色进行搜索。对每个未染色的节点分两种情况：当染黑色的情况下，不对其他节点产生影响；当染红色的情况下，要查找这个节点连接的所有边，找到相邻节点并直接规定为黑色。每当所有节点被染色完成就说明找到了一种结果，遍历所有可能后结束。

代码实现

import java.util.ArrayList;
import java.util.Scanner;class Main {public static class Side {int from;int to;public Side(int from, int to) {this.from = from;this.to = to;}}public static int[] pointsColor;public static ArrayList<Side> sideArrayList = new ArrayList<>();public static int result;public static void main(String[] args) {Scanner in = new Scanner(System.in);String[] heads = in.nextLine().split(" ");int pointsNum = Integer.parseInt(heads[0]);int sidesNum = Integer.parseInt(heads[1]);for (int i = 0; i < sidesNum; i++) {String[] strings = in.nextLine().split(" ");Side side = new Side(Integer.parseInt(strings[0]) - 1, Integer.parseInt(strings[1]) - 1);sideArrayList.add(side);}pointsColor = new int[pointsNum];colored(0);System.out.println(result);}//0无 1黑 2红public static void colored(int current) {if (current < pointsColor.length) {//未染色if (pointsColor[current] == 0) {//黑pointsColor[current] = 1;colored(current + 1);//红pointsColor[current] = 2;for (Side side : sideArrayList) {//临边黑if (side.from == current) {pointsColor[side.to] = 1;}if (side.to == current) {pointsColor[side.from] = 1;}}colored(current + 1);} else {//如果已经染过则直接查找下一个点colored(current + 1);}//搜索完之后回退pointsColor[current] = 0;} else if (current == pointsColor.length) {result += 1;}}
}