Leetcode 801 Solution

This article provides solution to leetcode question 801 (is-graph-bipartite)
Categories:
Tags:
Access this page by simply typing in "lcs 801" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/is-graph-bipartite

Solution

class UnionFindSet {
    vector<int> parent;

public:
    UnionFindSet(int size) {
        parent.resize(size);

        for (int i = 0; i < size; i++)
            parent[i] = i;
    }

    int Find(int i) {
        if (i == parent[i])
            return i;
        return parent[i] = Find(parent[i]);
    }

    void Union(int i, int j) {
        parent[Find(i)] = Find(j);
    }
};

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        UnionFindSet ufset((int)graph.size());

        for (int i = 0; i < graph.size(); i++)
        {
            if (graph[i].empty())
                continue;

            int ip = ufset.Find(i);
            int jp = ufset.Find(graph[i][0]);

            if (ip == jp)
                return false;

            for (int j = 0; j < graph[i].size(); j++)
                ufset.Union(jp, graph[i][j]);
        }

        return true;
    }
};