import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class q1080 { public static int[][] map; public static int[] color; public static boolean flag = false; public static void DFS(int index,int size){ if(flag) return; for(int i = 0 ;i < size;i++){ if(map[index][i] == 1){ if(color[i] == -1){ color[i] = color[index]==0?1:0; DFS(i,size); }else if(color[i] == color[index]){ flag = true; return; } } } } public static void BFS(int index,int size){ if(flag) return; Queue<Integer> que = new LinkedList<>(); que.offer(index); while(!que.isEmpty()){ int cur = que.poll(); int c = color[cur]==0?1:0; for(int i = 0;i < size;i++){ if(map[cur][i] == 1){ if(color[i] == -1){ color[i] = c; que.offer(i); }else if(color[i] == color[cur]){ flag = true; return; } } } } } public static void main(String[] args){ Scanner s = new Scanner(System.in); int n = s.nextInt(); map = new int[n][n]; color = new int[n]; for(int i = 0;i < n;i++){ color[i] = -1; } for(int i = 0;i<n;i++){ while(true){ int index = s.nextInt()-1; if(index == -1) break; map[i][index] = 1; map[index][i] = 1; } } for(int i = 0;i < n;i++){ if(color[i]==-1){ color[i] = 0; BFS(i,n); //DFS(i,n); } } if(flag){ System.out.println(-1); }else{ for(int i = 0;i<n;i++){ System.out.print(color[i]); } } } }用Java来换一种方法实现目的

这段代码实现的是判断一个无向图是否为二分图，即能否将所有节点用两种颜色染色，使得相邻的节点颜色不同。

如果要用 Java 实现另一种方法，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）。

以下是使用 DFS 的实现：

import java.util.Scanner;

public class q1080_dfs {
    public static int[][] map;
    public static int[] color;
    public static boolean flag = false;

    public static void dfs(int index, int size, int curColor) {
        color[index] = curColor;
        for (int i = 0; i < size; i++) {
            if (map[index][i] == 1) {
                if (color[i] == -1) {
                    dfs(i, size, 1 - curColor);
                } else if (color[i] == color[index]) {
                    flag = true;
                    return;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        map = new int[n][n];
        color = new int[n];
        for (int i = 0; i < n; i++) {
            color[i] = -1;
        }
        for (int i = 0; i < n; i++) {
            while (true) {
                int index = s.nextInt() - 1;
                if (index == -1)
                    break;
                map[i][index] = 1;
                map[index][i] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                dfs(i, n, 0);
            }
        }
        if (flag) {
            System.out.println(-1);
        } else {
            for (int i = 0; i < n; i++) {
                System.out.print(color[i]);
            }
        }
    }
}

以下是使用 BFS 的实现：

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

public class q1080_bfs {
    public static int[][] map;
    public static int[] color;
    public static boolean flag = false;

    public static void bfs(int index, int size) {
        Queue<Integer> que = new LinkedList<>();
        que.offer(index);
        color[index] = 0;
        while (!que.isEmpty()) {
            int cur = que.poll();
            int curColor = color[cur];
            for (int i = 0; i < size; i++) {
                if (map[cur][i] == 1) {
                    if (color[i] == -1) {
                        color[i] = 1 - curColor;
                        que.offer(i);
                    } else if (color[i] == curColor) {
                        flag = true;
                        return;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        map = new int[n][n];
        color = new int[n];
        for (int i = 0; i < n; i++) {
            color[i] = -1;
        }
        for (int i = 0; i < n; i++) {
            while (true) {
                int index = s.nextInt() - 1;
                if (index == -1)
                    break;
                map[i][index] = 1;
                map[index][i] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                bfs(i, n);
            }
        }
        if (flag) {
            System.out.println(-1);
        } else {
            for (int i = 0; i < n; i++) {
                System.out.print(color[i]);
            }
        }
    }
}

这两种实现方法的时间复杂度都是 O(n^2)，其中 n 是节点数。