前置知识：二分图以及它的判定

塔子哥找的一个比较高质量的讲解贴。大家想彻底搞清楚的可以去看看！

https://blog.csdn.net/m0_63997099/article/details/140763017

题面解释:

给定一个整数$n$表示员工人数，以及一个$n$行的邻接表数组，描述员工之间的同学或同团队关系。要求将这$n$个人分成两组，使得每组内没有同学或同团队的员工。输出按编号从小到大排序的最优分组方案，如果无法分组，则输出$-1$。

思路

单纯的二分图染色，处理完输入之后，开始进行染色，如果不是二分图进行标记停止染色。对染色后的图，存进两个数组里，比较一下谁小，在先输出谁即可。代码实现为dfs染色 $\\$ 对于一个无向图，起初图中所有顶点都是无色，我们从任意未染色顶点出发，对这个顶点进行染色，对于与这个顶点相邻的的顶点，有三种情况：$\\$ 1、未染色 那么将这个顶点染色，染与当前顶点不相同的颜色。$\\$ 2、已经染色但是当前顶点颜色不同 那么跳过该顶点$\\$ 3、已经染色但是与当前顶点相同。则该图不是一个二分图，返回失败。$\\$ 图中所有顶点已经进行染色，并且没有出现相邻顶点颜色相同的情况，则该图是一个二分图。

题解

1. 初始化：

   • 使用一个邻接表GoodRelationships存储员工之间的关系。
   • 使用一个color数组记录每个员工的颜色（或分组），0表示未染色，1和2表示不同的组。

2. 深度优先搜索（DFS）染色：

   • 从任意一个未染色的节点开始，进行DFS染色。
   • 对于当前节点u，我们将其染成颜色c。
   • 遍历所有与u相邻的节点v：
     • 如果v已染色且颜色与u相同，则说明图不是二分图，标记为失败。
     • 如果v未染色，则将其染成与u不同的颜色（3 - c）。

3. 检查每个节点：

   • 遍历所有节点，如果某个节点未染色，则从该节点开始DFS，确保所有分支都被检查。

4. 分组结果：

   • 根据color数组的值，将节点分为两个组。
   • 输出时比较两个组的第一个员工编号，以确定输出的顺序，确保输出最小的方案。

5. 边界条件：

   • 若在DFS过程中发现图不是二分图，直接输出$-1$。

$\\$

代码如下

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

// 定义图的邻接表，最大105个员工
vector<int> GoodRelationships[105];
int color[105];  // 记录每个节点的颜色，0表示未染色，1和2表示不同的组
bool is_bipartite = true;  // 判断是否为二分图

// 深度优先搜索函数，u为当前节点，c为当前颜色（组）
void dfs(int u, int c) {
    if (!is_bipartite) return;
    color[u] = c;
    for (int v : GoodRelationships[u]) {
        if (color[v] == c) {  // 如果相邻节点颜色相同，说明无法分组
            is_bipartite = false;
            return;
        }
        if (color[v] == 0) {  // 如果相邻节点未染色，则染上相反颜色
            dfs(v, 3 - c);
        }
    }
}

int main() {
    int n;  // n 表示员工数量
    cin >> n;
    cin.ignore();  // 忽略换行符

    // 输入邻接表数据
    for (int i = 0; i < n; i++) {
        string line;
        getline(cin, line);
        int num = 0;
        for (int j = 0; j < line.size(); j++) {
            if (line[j] == ' ') {
                GoodRelationships[i].push_back(num);
                num = 0;
            } else {
                num = num * 10 + (line[j] - '0');
            }
        }
        if (num != 0) {
            GoodRelationships[i].push_back(num);
        }
    }

    // 检查每个节点，如果未染色则从该节点开始dfs
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) {
            dfs(i, 1);  // 初始从颜色1开始
        }
    }

    // 如果无法分组，输出 -1
    if (!is_bipartite) {
        cout << -1 << endl;
        return 0;
    }

    vector<int> group1, group2;  // 分成两组

    // 按颜色将节点分组
    for (int i = 0; i < n; i++) {
        if (color[i] == 1) {
            group1.push_back(i);
        } else {
            group2.push_back(i);
        }
    }

    // 输出分组结果，选择编号最小的方案
    if (group1[0] > group2[0]) {
        swap(group1, group2);
    }

    for (int v : group1) {
        cout << v << " ";
    }
    cout << endl;
    for (int v : group2) {
        cout << v << " ";
    }
    cout << endl;

    return 0;
}

python

def dfs(u, color, adj, color_group):
    global is_bipartite
    if not is_bipartite:
        return
    color_group[u] = color
    for v in adj[u]:
        if color_group[v] == color:
            is_bipartite = False
            return
        if color_group[v] == 0:
            dfs(v, 3 - color, adj, color_group)

def main():
    import sys
    global is_bipartite
    is_bipartite = True

    n = int(sys.stdin.readline())
    adj = [[] for _ in range(n)]
    
    for i in range(n):
        line = sys.stdin.readline().strip()
        if line:
            numbers = list(map(int, line.split()))
            adj[i].extend(numbers)

    color_group = [0] * n  # 记录每个节点的颜色

    for i in range(n):
        if color_group[i] == 0:
            dfs(i, 1, adj, color_group)
            if not is_bipartite:
                break

    if not is_bipartite:
        print(-1)
        return

    group1 = []
    group2 = []

    for i in range(n):
        if color_group[i] == 1:
            group1.append(i)
        else:
            group2.append(i)

    # 确保 group1 的第一个元素编号更小
    if group1 and group2 and group1[0] > group2[0]:
        group1, group2 = group2, group1

    print(' '.join(map(str, group1)))
    print(' '.join(map(str, group2)))

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    // 定义图的邻接表
    static List<Integer>[] GoodRelationships;
    static int[] colorGroup;  // 记录每个节点的颜色，0表示未染色，1和2表示不同的组
    static boolean isBipartite = true;  // 判断图是否为二分图

    // 深度优先搜索函数，u为当前节点，c为当前颜色（组）
    public static void dfs(int u, int c) {
        if (!isBipartite) return;
        colorGroup[u] = c;
        for (int v : GoodRelationships[u]) {
            if (colorGroup[v] == c) {  // 如果相邻节点颜色相同，说明无法分组
                isBipartite = false;
                return;
            }
            if (colorGroup[v] == 0) {  // 如果相邻节点未染色，则染上相反颜色
                dfs(v, 3 - c);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // n 表示员工数量
        sc.nextLine();  // 忽略换行符

        // 初始化邻接表
        GoodRelationships = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            GoodRelationships[i] = new ArrayList<>();
        }

        // 输入邻接表数据
        for (int i = 0; i < n; i++) {
            String line = sc.nextLine().trim();
            if (!line.isEmpty()) {
                String[] parts = line.split("\\s+");
                for (String part : parts) {
                    int num = Integer.parseInt(part);
                    GoodRelationships[i].add(num);
                }
            }
        }

        colorGroup = new int[n];  // 初始化颜色数组

        // 检查每个节点，如果未染色则从该节点开始 DFS
        for (int i = 0; i < n; i++) {
            if (colorGroup[i] == 0) {
                dfs(i, 1);  // 初始从颜色1开始
                if (!isBipartite) break;
            }
        }

        // 如果无法分组，输出 -1
        if (!isBipartite) {
            System.out.println(-1);
            return;
        }

        List<Integer> group1 = new ArrayList<>();
        List<Integer> group2 = new ArrayList<>();

        // 按颜色将节点分组
        for (int i = 0; i < n; i++) {
            if (colorGroup[i] == 1) {
                group1.add(i);
            } else {
                group2.add(i);
            }
        }

        // 确保 group1 的第一个元素编号更小
        if (!group1.isEmpty() && !group2.isEmpty() && group1.get(0) > group2.get(0)) {
            List<Integer> temp = group1;
            group1 = group2;
            group2 = temp;
        }

        // 输出分组结果
        for (int v : group1) {
            System.out.print(v + " ");
        }
        System.out.println();
        for (int v : group2) {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}

题目内容

公司组织绩效互评，为了避免有同学或者同团队的人互相打高分，需要将员工分成两组分别打分。给定一个整数$n$和一个数组$GoodRelationShips[][]$，其中，$n$表示人数，数组$GoodRelationShips[][]$是一个邻接表，$GoodRelationShips[i]$的元素[$a,b,c$]代表员工$i$和员工$a，b，c$是同学或者同团队。

请将这$n$个人分成两组，使其每组不再有同学或者同团队的人。

$GoodRelationShips[][]$的长度范围为[$1,100$]。

$GoodRelationShips[i]$中的元素的范围为[$1,GoodRelationShips.length-1$]。

$GoodRelationShips[i]$不会包含i或者有重复的值。

图是无向的:如果$j$在$GoodRelationShips[1]$里边,那么$i$也会在 $GoodRelationShips[j]$里边。

说明

保证给出的图是联通图

输入描述

数组形式的员工关系邻接表，第一行数字代表有$N$个顶点，顶点编号从$0$开 始，后续接$N$行。第$i$行代表第$i-1$个顶点和他有关系的同学的顶点编号

输出描述

分组方案按照节点编号从小到大排序，如两个方案第一个节点相同，则按照第二个节点排序，以此类推;方案内部也按照编号从小到大排序。输出排序最靠前的一种方案，如无法分成符合条件的两组，则输出$-1$

如输出如下两种方案时，选择第一种方案，因为方案一的分组$2$第一个节点编号更小:

分组$1$：$1$

分组$2$：$2\ 3\ 4\ 5$

和

分组$1$：$1\ 2$

分组$2$：$3\ 4\ 5$

如输出如下两种方案时，选择第二种方案，因为方案二的分组$2$第一个节点编号更小:

分组$1$：$1\ 2$

分组$2$：$3\ 4\ 5$

和

分组$1$：$1\ 3$

分组$2$：$2\ 4\ 5$

样例1

输入

4
1 3
0 2
1 3
0 2

输出

0 2
1 3

说明

无向图如下：

样例2

输入

4
1 2 3
0 2
0 1 3
0 2

输出

-1

说明

无向图如下：