1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAXN 2001
6
7int* graph[MAXN];
8int graphSize[MAXN] = {0};
9int color[MAXN];
10
11bool bfs(int src) {
12    int queue[MAXN];
13    int front = 0, rear = 0;
14    queue[rear++] = src;
15    color[src] = 1;
16    while (front < rear) {
17        int node = queue[front++];
18        for (int i = 0; i < graphSize[node]; i++) {
19            int neighbor = graph[node][i];
20            if (color[neighbor] == 0) {
21                color[neighbor] = -color[node];
22                queue[rear++] = neighbor;
23            } else if (color[neighbor] == color[node]) {
24                return false;
25            }
26        }
27    }
28    return true;
29}
30
31bool possibleBipartition(int n, int** dislikes, int dislikesSize, int* dislikesColSize) {
32    for (int i = 1; i <= n; i++) {
33        graph[i] = (int*)malloc(sizeof(int) * (n + 1));
34    }
35
36    for (int i = 0; i < dislikesSize; i++) {
37        int u = dislikes[i][0];
38        int v = dislikes[i][1];
39        graph[u][graphSize[u]++] = v;
40        graph[v][graphSize[v]++] = u;
41    }
42
43    memset(color, 0, sizeof(color));
44
45    for (int i = 1; i <= n; i++) {
46        if (color[i] == 0) {
47            if (!bfs(i)) {
48                return false;
49            }
50        }
51    }
52
53    return true;
54}

1using System;
2using 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;
    }
}