[三星电子]算法题--两种颜色涂无向图（bfs）

题目

题目描述：
给一无向图中各个节点绘色，一共只有两种颜色，使其满足相邻节点颜色不同，并输出其中一种颜色的节点个数及序号；如果不满足，则输出-1。

示例：

第一行输入节点个数V和边数E，第二行输入E条边（每条边对应的两个节点），例如：

7 9

1 2 1 4 2 3 3 4 2 5 4 5 2 6 5 7 6 7

例图：

代码与解析

这个算法的目的是检测一个给定的图是否包含一个二分图。二分图是一种特殊的图，它的顶点集可以被划分为两个互不相交的子集，使得每条边的两个顶点都属于不同的子集。

算法的基本思路是使用广度优先搜索（BFS） 来遍历图，同时维护一个颜色数组来标记每个节点的颜色。如果图中存在一个二分图，那么存在一个节点，其所有邻接节点都与它颜色不同。如果图中不存在二分图，那么存在一个节点，其所有邻接节点都与它颜色相同。

具体步骤如下：

1. 初始化一个队列和一个标志位。队列用于存储待处理的节点，标志位用于检测是否找到了二分图。

2. 将起始节点加入队列，并将其颜色设为1（假设开始时所有节点都是白色）。

3. 进入循环，直到队列为空：

   • 从队列中取出一个节点，并检查其所有未被处理的邻接节点。
   • 如果某个邻接节点未被处理且颜色与当前节点不同，将其颜色设为与当前节点颜色相反的颜色，并将其加入队列。
   • 如果某个邻接节点未被处理且颜色与当前节点相同，将标志位设为true并跳出循环。

4. 如果循环结束时标志位仍为false，说明图中存在一个二分图。否则，图中不存在二分图。

5. 如果图中存在二分图，计算并输出属于同一子集的节点数。

6. 如果图中不存在二分图，输出节点的数量。

这个算法的时间复杂度是O(V + E)，其中V是顶点数，E是边数。这是因为每个顶点和边都只会被访问和处理一次。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Nodirections {
    static int[][] a = new int[1001][1001]; // 存储图的邻接关系
    // 0为默认白色,1代表黑色，同时[0]代表颜色为？[1]代表是否被设置
    static int[][] color = new int[1001][2]; // 记录节点的颜色和状态
    static int[] num = new int[1001]; // 记录黑色节点的编号
    static int num1 = 0; // 记录黑色节点数量

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int v, e;
        System.out.println("请输入节点数和边数： ");
        v = in.nextInt(); // 读取节点数
        e = in.nextInt(); // 读取边数
        for (int i = 0; i < e; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            a[x][y] = 1;
            a[y][x] = 1; // 无向图，设置两个方向的邻接关系
        }
        Queue<Integer> q = new LinkedList<>();
        q.add(1); // 添加第一个节点1
        boolean b = false; // 记录是否出现颜色冲突
        while (!q.isEmpty()) {
            int curV = q.poll();
            int temp = color[curV][0]; // 当前节点的颜色
            color[curV][1] = 2; // 设置节点状态为已遍历
            for (int j = 1; j <= v; j++) {
                if (a[curV][j] == 0) continue; // 无邻接关系，跳过
                // j节点与cur节点连通并且颜色未被设置
                if (color[j][1] == 0) {
                    color[j][0] = 1 - temp; // 颜色取反
                    color[j][1] = 2; // 设置节点状态
                    q.add(j);
                }
                if (color[j][1] == 2) {
                    if (color[j][0] != (1 - temp)) {
                        b = true;
                        break;
                    }
                }
            }
            if (b) {
                num1 = -1; // 出现颜色冲突，标记为-1
                break;
            }
        }
        if (!b) {
            num1 = 0;
            for (int k = 1; k <= v; k++) {
                if (color[k][0] == 1) {
                    num[num1++] = k; // 记录黑色节点的编号
                }
            }
        }
        System.out.print("#：" + num1); // 输出黑色节点的数量
        for (int d = 0; d < num1; d++) {
            System.out.print(" " + num[d]); // 输出黑色节点的编号
        }
        System.out.println();
    }
}