Graph2/GraphRelabel.hpp

View this file on GitHub
Last update: 2023-07-17 18:02:31+09:00
Include: #include "Graph2/GraphRelabel.hpp"

Depends on

Code

#include "./GraphTemplate.hpp"
#include "../UnionFind/UnionFind.hpp"

template<typename T>
vector<Graph<T>> GraphRelabel(Graph<T> G){
    UnionFind uf(G.V);
    for(int i=0;i<G.V;i++)for(auto &e:G[i]) uf.unite(e.from,e.to);
    
    vector<vector<int>> vertice(G.V);
    for(int i=0;i<G.V;i++) vertice[uf.root(i)].push_back(i);

    vector<Graph<T>> ret;
    for(auto &w:vertice){
        if(w.empty()) continue;
        Graph<T> subG(w.size());
        for(int &x:w){
            int u=lower_bound(begin(w),end(w),x)-begin(w);
            for(auto &e:G[x]){
                int v=lower_bound(begin(w),end(w),e.to)-begin(w);
                subG.add_directed_edge(u,v,e.w);
            }
        }
        ret.push_back(subG);
    }
    return ret;
}

#line 1 "Graph2/GraphTemplate.hpp"



// graph template
// ref : https://ei1333.github.io/library/graph/graph-template.hpp
template<typename T=int>
struct Edge{
    int from,to;
    T w;
    int idx;
    Edge()=default;
    Edge(int from,int to,T w=1,int idx=-1):from(from),to(to),w(w),idx(idx){}
    operator int() const{return to;}
};

template<typename T=int>
struct Graph{
    vector<vector<Edge<T>>> g;
    int V,E;
    Graph()=default;
    Graph(int n):g(n),V(n),E(0){}

    int size(){
        return (int)g.size();
    }
    void resize(int k){
        g.resize(k);
        V=k;
    }
    inline const vector<Edge<T>> &operator[](int k)const{
        return (g.at(k));
    }
    inline vector<Edge<T>> &operator[](int k){
        return (g.at(k));
    }
    void add_directed_edge(int from,int to,T cost=1){
        g[from].emplace_back(from,to,cost,E++);
    }
    void add_edge(int from,int to,T cost=1){
        g[from].emplace_back(from,to,cost,E);
        g[to].emplace_back(to,from,cost,E++);
    }
    void read(int m,int pad=-1,bool weighted=false,bool directed=false){
        for(int i=0;i<m;i++){
            int u,v;cin>>u>>v;
            u+=pad,v+=pad;
            T w=T(1);
            if(weighted) cin>>w;
            if(directed) add_directed_edge(u,v,w);
            else         add_edge(u,v,w);
        }
    }
};


#line 1 "UnionFind/UnionFind.hpp"
struct UnionFind{
    private:
    vector<int> par,siz;

    public:
    int con;
    UnionFind(int n):par(n),siz(n,1),con(n){
        iota(begin(par),end(par),0);
    }
    int root(int x){
        return (par[x]==x?x:(par[x]=root(par[x])));
    }
    bool sameroot(int x,int y){
        return root(x)==root(y);
    }
    bool unite(int x,int y){
        x=root(x);y=root(y);
        if(x==y) return false;
        if(siz[x]<siz[y])swap(x,y);
        siz[x]+=siz[y];
        par[y]=x;
        con--;
        return true;
    }
    int size(int x){
        return siz[root(x)];
    }
};
#line 3 "Graph2/GraphRelabel.hpp"

template<typename T>
vector<Graph<T>> GraphRelabel(Graph<T> G){
    UnionFind uf(G.V);
    for(int i=0;i<G.V;i++)for(auto &e:G[i]) uf.unite(e.from,e.to);
    
    vector<vector<int>> vertice(G.V);
    for(int i=0;i<G.V;i++) vertice[uf.root(i)].push_back(i);

    vector<Graph<T>> ret;
    for(auto &w:vertice){
        if(w.empty()) continue;
        Graph<T> subG(w.size());
        for(int &x:w){
            int u=lower_bound(begin(w),end(w),x)-begin(w);
            for(auto &e:G[x]){
                int v=lower_bound(begin(w),end(w),e.to)-begin(w);
                subG.add_directed_edge(u,v,e.w);
            }
        }
        ret.push_back(subG);
    }
    return ret;
}