1#include <vector>
2#include <queue>
3using namespace std;
4
5bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
6    vector<vector<int>> graph(n + 1);
7    vector<int> color(n + 1, 0);
8    for (const auto& edge : dislikes) {
9        graph[edge[0]].push_back(edge[1]);
10        graph[edge[1]].push_back(edge[0]);
11    }
12    for (int i = 1; i <= n; ++i) {
13        if (!color[i]) {
14            queue<int> q;
15            q.push(i);
16            color[i] = 1;
17            while (!q.empty()) {
18                int node = q.front(); q.pop();
19                for (int neighbor : graph[node]) {
20                    if (!color[neighbor]) {
21                        color[neighbor] = -color[node];
22                        q.push(neighbor);
23                    } else if (color[neighbor] == color[node]) {
24                        return false;
25                    }
26                }
27            }
28        }
29    }
30    return true;
31}

1using System;
using System.Collections.Generic;

public class Solution {
    public bool PossibleBipartition(int n, int[][] dislikes) {
        var graph = new List<int>[n + 1];
        for (int i = 1; i <= n; i++)
            graph[i] = new List<int>();

        foreach (var edge in dislikes) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }

        var color = new int[n + 1];

        bool Dfs(int node, int c) {
            color[node] = c;
            foreach (int neighbor in graph[node]) {
                if (color[neighbor] == 0) {
                    if (!Dfs(neighbor, -c)) return false;
                } else if (color[neighbor] == color[node]) {
                    return false;
                }
            }
            return true;
        }

        for (int i = 1; i <= n; i++) {
            if (color[i] == 0) {
                if (!Dfs(i, 1)) {
                    return false;
                }
            }
        }
        return true;
    }
}