[LeetCode] Possible Bipartition

Problem: We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.

Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.

Example:

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4] and group2 [2,3].

Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

Input: n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false

Approach: This is clearly a bipartite graph problem. We can use coloring approach to solve it.

Implementation in C#:

    public bool PossibleBipartition(int n, int[][] dislikes)

    {

        var dislikeGraph = new Dictionary<int, List<int>>();

        foreach(int[] dislike in dislikes)

        {

            if (!dislikeGraph.ContainsKey(dislike[0]))

            {

                dislikeGraph[dislike[0]] = new List<int>();

            }

            if (!dislikeGraph.ContainsKey(dislike[1]))

            {

                dislikeGraph[dislike[1]] = new List<int>();

            }

            dislikeGraph[dislike[0]].Add(dislike[1]);

            dislikeGraph[dislike[1]].Add(dislike[0]);

        }

        int[] color = new int[n + 1];

        for (int i = 1; i <= n; ++i)

        {

            if (color[i] == 0)

            {

                if (!this.DFS(i, 1, dislikeGraph, color))

                {

                    return false;

                }

            }

        }

        return true;

    }

    private bool DFS(int node,

                int currColor,

                Dictionary<int, List<int>> dislikeGraph,

                int[] color)

    {

        color[node] = currColor;

        if (dislikeGraph.ContainsKey(node))

        {

            foreach(int neighbour in dislikeGraph[node])

            {

                if (color[neighbour] == color[node])

                {

                    return false;

                }

                if (color[neighbour] == 0)

                {

                    DFS(neighbour, -color[node], dislikeGraph, color);

                }

            }

        }

        return true;

    }

Complexity: O(n)