红黑图-华为OD机试 2023

题目描述

注意：不能保证所有节点都是连通的。

示例1：

输入：

4 4

1 2

2 4

3 4

1 3

输出：

7

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

结题思路

python代码

# 这个我还没搞清楚，有大佬按照下面这个思路，翻译一下Python，粘贴到评论处吗？

java代码

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