test/library_checker/graph/connected_components_of_complement_graph.test.cpp

• View this file on GitHub
• Last update: 2024-11-01 00:31:19+09:00
• Problem: https://judge.yosupo.jp/problem/connected_components_of_complement_graph

Depends on

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

Code

#define PROBLEM "https://judge.yosupo.jp/problem/connected_components_of_complement_graph"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/graph/connected_components_of_complement_graph.hpp"

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<vector<int>> G(n);
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    vector<vector<int>> ans = connectedComponentsOfComplementGraph(G);
    cout << ans.size() << "\n";
    for(auto &v : ans){
        cout << v.size() << " ";
        for(auto x : v){
            cout << x << " ";
        }
        cout << "\n";
    }
}

#line 1 "test/library_checker/graph/connected_components_of_complement_graph.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/connected_components_of_complement_graph"
#include <bits/stdc++.h>
using namespace std;

#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;
}
#line 6 "test/library_checker/graph/connected_components_of_complement_graph.test.cpp"

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<vector<int>> G(n);
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    vector<vector<int>> ans = connectedComponentsOfComplementGraph(G);
    cout << ans.size() << "\n";
    for(auto &v : ans){
        cout << v.size() << " ";
        for(auto x : v){
            cout << x << " ";
        }
        cout << "\n";
    }
}

Back to top page