简单的python代码

n = int(input())
L = []
for _ in range(n):
    L.append(list(map(int,input().split())))
t=1
a = [0]
b = L[0]
for i in range(1,n):
    if i in a and i in b:
        t=0
        break
    if i in a:
        b+=L[i]
    elif i in b:
        a+=L[i]
if t:
    print(*list(set(a)))
    print(*list(set(b)))    
else:
    print(-1)

# BFS
from collections import deque

n = int(input())

colors = [-1 for _ in range(n)]
graph = [list(map(int, input().split())) for _ in range(n)]

conflict = 0

g1, g2 = [0], []

for i in range(n):
    queue = deque([i])
    if colors[i] == -1:
        colors[i] = 0
    
    while queue:
        node = queue.popleft()
    
        for neighbor in graph[node]:
            if colors[neighbor] == colors[node]:
                conflict = 1

            elif colors[neighbor] == -1:
                colors[neighbor] = 1 - colors[node]
                queue.append(neighbor)
                if colors[node] == 0:
                    g2.append(neighbor)
                elif colors[node] == 1:
                    g1.append(neighbor)

if conflict:
    print(-1)
else:
    print(*sorted(g1))
    print(*sorted(g2))

def erfen(n):
    # 初始染色值为0
    color = [0 for _ in range(n)]
    # 把输入处理为双层列表
    l = []
    for i in range(n):
        nei = list(map(int, input().split()))
        l.append(nei)
    # 对于每个节点：未染色则染色为1
    for node in range(n):
        if color[node]==0:color[node]=1
        # 采用bfs对相邻节点进行处理
        # 如果相邻节点颜色相同，则无法分为两组，返回-1
        # 如果相邻节点颜色不同，继续即可
        # 如果相邻节点未被访问过，则设置为与当前节点颜色不同的值
        q = []
        q.append(node)
        while q:
            cur = q.pop(0)
            for neighbor in l[cur]:
                if color[neighbor]==color[cur]: return -1
                elif color[neighbor]==-color[cur]:continue
                else:
                    color[neighbor]=-color[cur]
                    q.append(neighbor)
    # 最终颜色为1的为一组，颜色为0的为一组
    list1 = [i for i, val in enumerate(color) if val == 1]
    list2 = [i for i, val in enumerate(color) if val == -1 ]
    
    list1 = sorted(list1)
    list2 = sorted(list2)

    group1 = " ".join(str(num) for num in list1)
    group2 = " ".join(str(num) for num in list2)
    return group1, group2

n = int(input())  
group1,group2 = erfen(n)
if group1 != -1:
    print(group1)
    print(group2)
else:
    print(-1)
    

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
using namespace std;

struct edge {
    int to;
    int weight;
};

int n;
bool flag = true;
vector<vector<edge>> graph;
vector<int> color;
void add (int from, int to, int weight) {
        graph[from].push_back({to, weight});
}

void dfs(int index, int c) {
    if (flag == false) {
        return;
    }
    color[index] = c;
    for (int i = 0; i < graph[index].size(); i++) {
        if (color[graph[index][i].to] == 0) {
            dfs(graph[index][i].to, 3 - c);
        } else {
            if (color[graph[index][i].to] == 3 - c) continue;
            else {
                flag = false;
                return;
            }
        }
    }
}

int main() {
    cin >> n;
    graph.resize(n + 1);
    color.resize(n + 1, 0);
    string s;
    getline(cin, s);  // 读取换行符
    for (int i = 0; i < n; i++) {
        getline(cin, s);  // 读取每一行
        stringstream ss(s);
        int x;
        while (ss >> x) {
            add(i, x, 1);  // 添加无向边
            add(x, i, 1);
        }
    }
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) {
            dfs(i, 1);
        } else {
            continue;
        }
    }
    if (flag == false) cout << -1 << endl;
    else {
        vector<int> ling;
        vector<int> yi;
        for (int i = 0; i < n; i++) {
            if (color[i] == 1) ling.push_back(i);
            else yi.push_back(i);
        }
        if (yi[0] > ling[0]) {
            for (int i = 0; i < ling.size(); i++) cout << ling[i] << " ";
            cout << endl;
            for (int i = 0; i < yi.size(); i++) cout << yi[i] << " ";
        } else {
            for (int i = 0; i < yi.size(); i++) cout << yi[i] << " ";
            cout << endl;
            for (int i = 0; i < ling.size(); i++) cout << ling[i] << " ";
        }
    }
    return 0;
}

package realpbms.dfs;

import java.util.Scanner;

/**
 * 栽华子手上了，娘的
 * 二分图判定
 */
public class P1467 {

    private static boolean isBiGraph = true;

    private static boolean[] color;

    private static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] a = new int[n][];

        sc.nextLine();

        for (int i = 0; i < n; i++) {
            String[] row = sc.nextLine().split(" ");
            a[i] = new int[row.length];
            for (int j = 0; j < row.length; j++) {
                a[i][j] = Integer.parseInt(row[j]);
            }
        }

        if (isBipartite(a)) {
            StringBuilder sb1 = new StringBuilder();
            StringBuilder sb2 = new StringBuilder();
            for (int i = 0; i < color.length; i++) {
                if (i != color.length - 1) {
                    if (color[i]) {
                        sb1.append(i).append(" ");
                    } else {
                        sb2.append(i).append(" ");
                    }
                } else {
                    if (color[i]) {
                        sb1.append(i);
                    } else {
                        sb2.append(i);
                    }
                }
            }
            if (sb1.toString().compareTo(sb2.toString()) < 0) {
                System.out.println(sb1);
                System.out.println(sb2);
            } else {
                System.out.println(sb2);
                System.out.println(sb1);
            }
        } else {
            System.out.println(-1);
        }


    }

    public static boolean isBipartite(int[][] graph) {

        color = new boolean[graph.length];

        visited = new boolean[graph.length];

        for (int i = 0; i < graph.length; i++) {
            if (!visited[i]) {
                dfs(graph, i);
            }
        }

        return isBiGraph;

    }

    private static void dfs(int[][] graph, int cur) {
        if (!isBiGraph) {
            return;
        }

        visited[cur] = true;

        for (int next : graph[cur]) {
            if (visited[next]) {
                if (color[next] == color[cur]) {
                    isBiGraph = false;
                    return;
                }
            } else {
                color[next] = !color[cur];
                dfs(graph, next);
            }
        }


    }


}

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

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

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();
    }
}