test/library_checker/graph/connected_components_of_complement_graph_1.test.cpp

• View this file on GitHub
• Last update: 2024-05-06 22:04:04+09:00
• Problem: https://judge.yosupo.jp/problem/connected_components_of_complement_graph

Depends on

• lib/data_structure/fast_deque.hpp

Code

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

#include "../../../lib/data_structure/fast_deque.hpp"

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

    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;
    vector<bool> used(n), 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;
        FastDeque<int> q;
        q.push_back(i);
        while(!q.empty()){
            int x = q.front(); q.pop_front();
            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_back(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);
    }
    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_1.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/connected_components_of_complement_graph"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/data_structure/fast_deque.hpp"

template <typename T>
struct FastDeque{
    int l = 1, r = 0;
    vector<T> L, R;

    FastDeque(){}

    T front(){
        if(l <= 0){
            return L[-l];
        } else{
            return R[l - 1];
        }
    }

    void push_front(int v){
        l--;
        if(l <= 0){
            if((int) L.size() == -l){
                L.push_back(v);
            } else{
                L[-l] = v;
            }
        } else{
            R[l - 1] = v;
        }
    }

    void pop_front(){
        l++;
    }

    T back(){
        if(r <= 0){
            return L[-r];
        } else{
            return R[r - 1];
        }
    }

    void push_back(int v){
        if(r < 0){
            L[-r - 1] = v;
        } else{
            if((int) R.size() == r){
                R.push_back(v);
            } else{
                R[r] = v;
            }
        }
        r++;
    }

    void pop_back(){
        r--;
    }

    bool empty(){
        return (r - l + 1) == 0;
    }

    size_t size(){
        return (r - l + 1);
    }
};
#line 6 "test/library_checker/graph/connected_components_of_complement_graph_1.test.cpp"

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

    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;
    vector<bool> used(n), 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;
        FastDeque<int> q;
        q.push_back(i);
        while(!q.empty()){
            int x = q.front(); q.pop_front();
            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_back(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);
    }
    cout << ans.size() << "\n";
    for(auto &v : ans){
        cout << v.size() << " ";
        for(auto x : v){
            cout << x << " ";
        }
        cout << "\n";
    }
}

Back to top page