graph/connected_components.hpp

• View this file on GitHub
• Last update: 2022-07-30 11:55:56+09:00
• Include: #include "graph/connected_components.hpp"

Code

#pragma once
#include <queue>
#include <utility>
#include <vector>

class ConnectedComponents {
    std::vector<int> number;
    int comp;

public:
    template <typename G>
    ConnectedComponents(const G &graph) :
        number((int) graph.size(), -1), comp(0) {
        std::queue<int> que;
        for (int i = 0; i < (int) graph.size(); ++i) {
            if (number[i] != -1) {
                continue;
            }
            que.push(i);
            number[i] = comp;
            while (!que.empty()) {
                int v = que.front();
                que.pop();
                for (const auto &e : graph[v]) {
                    if (number[(int) e] == -1) {
                        number[(int) e] = number[v];
                        que.push((int)e);
                    }
                }
            }
            ++comp;
        }
    }

    int operator[](int v) const {
        assert(v >= 0 && v < (int) number.size());
        return number[v];
    }

    std::vector<std::vector<int>> groups() const {
        std::vector<std::vector<int>> ret(comp);
        for (int i = 0; i < (int) number.size(); ++i)
            ret[number[i]].push_back(i);
        return ret;
    }

    int components() const {
        return comp;
    }
};

#line 2 "graph/connected_components.hpp"
#include <queue>
#include <utility>
#include <vector>

class ConnectedComponents {
    std::vector<int> number;
    int comp;

public:
    template <typename G>
    ConnectedComponents(const G &graph) :
        number((int) graph.size(), -1), comp(0) {
        std::queue<int> que;
        for (int i = 0; i < (int) graph.size(); ++i) {
            if (number[i] != -1) {
                continue;
            }
            que.push(i);
            number[i] = comp;
            while (!que.empty()) {
                int v = que.front();
                que.pop();
                for (const auto &e : graph[v]) {
                    if (number[(int) e] == -1) {
                        number[(int) e] = number[v];
                        que.push((int)e);
                    }
                }
            }
            ++comp;
        }
    }

    int operator[](int v) const {
        assert(v >= 0 && v < (int) number.size());
        return number[v];
    }

    std::vector<std::vector<int>> groups() const {
        std::vector<std::vector<int>> ret(comp);
        for (int i = 0; i < (int) number.size(); ++i)
            ret[number[i]].push_back(i);
        return ret;
    }

    int components() const {
        return comp;
    }
};

Back to top page