package cn.iocoder.yudao.framework.common.thealgorithms.backtracking;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

///**
// * @author Bama Charan Chhandogi (https://github.com/BamaCharanChhandogi)
// */
//class Node {
//    int color = 1;
//    Set<Integer> edges = new HashSet<Integer>();
//}
//
//public final class MColoring {
//    private MColoring() {
//    }
//    static int possiblePaint(ArrayList<Node> nodes, int n, int m) {
//
//        // Create a visited array of n nodes
//        ArrayList<Integer> visited = new ArrayList<Integer>();
//        for (int i = 0; i < n + 1; i++) {
//            visited.add(0);
//        }
//
//        // maxColors used till now are 1 as
//        // all nodes are painted color 1
//        int maxColors = 1;
//
//        for (int sv = 1; sv <= n; sv++) {
//            if (visited.get(sv) > 0) {
//                continue;
//            }
//
//            // If the starting point is unvisited,
//            // mark it visited and push it in queue
//            visited.set(sv, 1);
//            Queue<Integer> q = new LinkedList<>();
//            q.add(sv);
//
//            // BFS
//            while (q.size() != 0) {
//                int top = q.peek();
//                q.remove();
//
//                // Checking all adjacent nodes
//                // to "top" edge in our queue
//                for (int it : nodes.get(top).edges) {
//
//                    // If the color of the
//                    // adjacent node is same, increase it by
//                    // 1
//                    if (nodes.get(top).color == nodes.get(it).color) {
//                        nodes.get(it).color += 1;
//                    }
//
//                    // If number of colors used exceeds m,
//                    // return 0
//                    maxColors = Math.max(maxColors, Math.max(nodes.get(top).color, nodes.get(it).color));
//                    if (maxColors > m) {
//                        return 0;
//                    }
//
//                    // If the adjacent node is not visited,
//                    // mark it visited and push it in queue
//                    if (visited.get(it) == 0) {
//                        visited.set(it, 1);
//                        q.add(it);
//                    }
//                }
//            }
//        }
//        return 1;
//    }
//}



/**
 * 节点类，表示图中的一个节点及其边
 */
class Node {
    int color = 1; // 默认颜色为1
    Set<Integer> edges = new HashSet<Integer>(); // 存储与该节点相连的边
}

/**
 * MColoring类包含解决M着色问题的方法
 */
public final class MColoring {
    private MColoring() {
    }

    /**
     * 判断是否可能用m种颜色为图的所有节点着色，使得相邻节点颜色不同
     * @param nodes 图的节点列表
     * @param n 节点数量
     * @param m 颜色数量
     * @return 如果可以用m种颜色着色，则返回1；否则返回0
     */
    static int possiblePaint(ArrayList<Node> nodes, int n, int m) {

        // 创建一个访问数组，记录n个节点的访问状态
        ArrayList<Integer> visited = new ArrayList<Integer>();
        for (int i = 0; i < n + 1; i++) {
            visited.add(0);
        }

        // 目前使用的最大颜色数为1，因为所有节点初始都涂上颜色1
        int maxColors = 1;

        // 遍历所有节点
        for (int sv = 1; sv <= n; sv++) {
            if (visited.get(sv) > 0) {
                continue; // 如果已访问，跳过
            }

            // 如果起始点未被访问，标记为已访问并加入队列
            visited.set(sv, 1);
            Queue<Integer> q = new LinkedList<>();
            q.add(sv);

            // 广度优先搜索（BFS）
            while (q.size() != 0) {
                int top = q.peek();
                q.remove();

                // 检查队列顶部节点的所有相邻节点
                for (int it : nodes.get(top).edges) {

                    // 如果相邻节点的颜色相同，则增加1
                    if (nodes.get(top).color == nodes.get(it).color) {
                        nodes.get(it).color += 1;
                    }

                    // 如果使用的颜色数超过m，返回0
                    maxColors = Math.max(maxColors, Math.max(nodes.get(top).color, nodes.get(it).color));
                    if (maxColors > m) {
                        return 0;
                    }

                    // 如果相邻节点未被访问，标记为已访问并加入队列
                    if (visited.get(it) == 0) {
                        visited.set(it, 1);
                        q.add(it);
                    }
                }
            }
        }
        return 1; // 如果所有节点都能正确着色，返回1
    }
}

