题目
题目描述：
给一无向图中各个节点绘色，一共只有两种颜色，使其满足相邻节点颜色不同，并输出其中一种颜色的节点个数及序号；如果不满足，则输出-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（假设开始时所有节点都是白色）。
-
进入循环，直到队列为空：
- 从队列中取出一个节点，并检查其所有未被处理的邻接节点。
- 如果某个邻接节点未被处理且颜色与当前节点不同，将其颜色设为与当前节点颜色相反的颜色，并将其加入队列。
- 如果某个邻接节点未被处理且颜色与当前节点相同，将标志位设为true并跳出循环。
-
如果循环结束时标志位仍为false，说明图中存在一个二分图。否则，图中不存在二分图。
-
如果图中存在二分图，计算并输出属于同一子集的节点数。
-
如果图中不存在二分图，输出节点的数量。
这个算法的时间复杂度是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();
}
}
