Connected Components of Complement Graph (補グラフの連結成分分解)
(lib/graph/connected_components_of_complement_graph.hpp)

• View this file on GitHub
• Last update: 2024-11-01 00:31:19+09:00
• Include: #include "lib/graph/connected_components_of_complement_graph.hpp"

Connected Components of Complement Graph (補グラフの連結成分分解)

概要

グラフ $G$ の補グラフについてのそれぞれの連結成分を求めます。

計算量

頂点数を $V$、辺の数を $E$ とすると、$\mathrm{O}(E + V)$

Verified with

• test/library_checker/graph/connected_components_of_complement_graph.test.cpp

Code

#pragma once

/**
 * @brief Connected Components of Complement Graph (補グラフの連結成分分解)
 * @docs docs/graph/connected_components_of_complement_graph.md
 */

template <typename T>
vector<vector<int>> connectedComponentsOfComplementGraph(vector<vector<T>> &G){
    int n = (int) G.size();
    vector<vector<int>> ans;
    vector<bool> used(n, false), reach(n, true);
    vector<int> s(n);
    iota(s.begin(), s.end(), 0);
    for(int i = 0; i < n; i++){
        if(used[i]) continue;
        vector<int> v;
        queue<int> q;
        q.push(i);
        while(!q.empty()){
            int x = q.front(); q.pop();
            if(used[x]) continue;
            used[x] = true;
            v.push_back(x);
            for(auto y : G[x]){
                reach[y] = false;
            }
            vector<int> ts;
            while(!s.empty()){
                if(reach[s.back()]){
                    q.push(s.back());
                } else{
                    ts.push_back(s.back());
                }
                s.pop_back();
            }
            swap(s, ts);
            for(auto y : G[x]){
                reach[y] = true;
            }
        }
        ans.push_back(v);
    }
    return ans;
}

#line 2 "lib/graph/connected_components_of_complement_graph.hpp"

/**
 * @brief Connected Components of Complement Graph (補グラフの連結成分分解)
 * @docs docs/graph/connected_components_of_complement_graph.md
 */

template <typename T>
vector<vector<int>> connectedComponentsOfComplementGraph(vector<vector<T>> &G){
    int n = (int) G.size();
    vector<vector<int>> ans;
    vector<bool> used(n, false), reach(n, true);
    vector<int> s(n);
    iota(s.begin(), s.end(), 0);
    for(int i = 0; i < n; i++){
        if(used[i]) continue;
        vector<int> v;
        queue<int> q;
        q.push(i);
        while(!q.empty()){
            int x = q.front(); q.pop();
            if(used[x]) continue;
            used[x] = true;
            v.push_back(x);
            for(auto y : G[x]){
                reach[y] = false;
            }
            vector<int> ts;
            while(!s.empty()){
                if(reach[s.back()]){
                    q.push(s.back());
                } else{
                    ts.push_back(s.back());
                }
                s.pop_back();
            }
            swap(s, ts);
            for(auto y : G[x]){
                reach[y] = true;
            }
        }
        ans.push_back(v);
    }
    return ans;
}

Back to top page