library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Bipolar Orientation
(Graph/bipolar.hpp)

• View this file on GitHub
• Last update: 2024-06-22 00:56:30+09:00
• Include: #include "Graph/bipolar.hpp"

Depends on

• Linked List (DataStructure/linkedlist.hpp)

Code

#pragma once
#include "DataStructure/linkedlist.hpp"

vector<int> BipolarOrientation(int n,vector<vector<int>>& g,int s,int t){
    int cur=1;
    vector<int> par(n),ord(n,-1),low(n),path;
    auto dfs=[&](auto& dfs,int v)->void{
        ord[v]=cur++;
        low[v]=v;
        path.push_back(v);
        for(auto& to:g[v]){
            if(ord[to]==-1){
                dfs(dfs,to);
                par[to]=v;
                if(ord[low[to]]<ord[low[v]]){
                    low[v]=low[to];
                }
            }
            else if(ord[to]<ord[low[v]])low[v]=to;
        }
    };
    ord[s]=0;
    dfs(dfs,t);
    if(SZ(path)!=n-1)return {};
    path.erase(path.begin());
    
    const bool plus=1,minus=0;
    vector<int> sign(n);
    LinkedList<int> LL;
    vector<LinkedList<int>::Node*> nodes(n);
    nodes[s]=LL.insert_front(nullptr,s);
    nodes[t]=LL.insert_back(nodes[s],t);
    
    for(auto& v:path){
        if(sign[low[v]]==minus){
            nodes[v]=LL.insert_front(nodes[par[v]],v);
            sign[par[v]]=plus;
        }
        else{
            nodes[v]=LL.insert_back(nodes[par[v]],v);
            sign[par[v]]=minus;
        }
    }
    auto perm=LL.dump(); // index:vertices
    vector<int> ret(n);
    rep(i,0,n)ret[perm[i]]=i;

    // check
    vector<int> FROM(n),TO(n);
    FROM[s]=TO[t]=1;
    for(auto& v:perm){
        if(!FROM[v])return {};
        for(auto& to:g[v])if(ret[v]<ret[to]){
            FROM[to]=1;
        }
    }
    reverse(ALL(perm));
    for(auto& v:perm){
        if(!TO[v])return {};
        for(auto& to:g[v])if(ret[v]>ret[to]){
            TO[to]=1;
        }
    }

    return ret;
}

/**
 * @brief Bipolar Orientation
 */

#line 2 "DataStructure/linkedlist.hpp"

template<typename T>struct LinkedList{
    struct Node{
        T val;
        Node* head,*tail;
        Node(){}
        Node(T v):val(v),head(nullptr),tail(nullptr){}
    };
    Node* front;
    LinkedList():front(nullptr){}
    Node* insert_back(Node* v,T x){
        if(v==nullptr){
            return front=new Node(x);
        }
        auto to=v->tail;
        auto add=new Node(x);
        v->tail=add;
        add->head=v;
        add->tail=to;
        if(to)to->head=add;
        return add;
    }
    Node* insert_front(Node* v,T x){
        if(v==nullptr){
            return front=new Node(x);
        }
        auto to=v->head;
        auto add=new Node(x);
        if(to)to->tail=add;
        add->head=to;
        add->tail=v;
        v->head=add;
        return add;
    }
    vector<T> dump(){
        vector<T> ret;
        Node* cur=front;
        while(cur){
            ret.push_back(cur->val);
            cur=cur->tail;
        }
        return ret;
    }
};  

/**
 * @brief Linked List
 */
#line 3 "Graph/bipolar.hpp"

vector<int> BipolarOrientation(int n,vector<vector<int>>& g,int s,int t){
    int cur=1;
    vector<int> par(n),ord(n,-1),low(n),path;
    auto dfs=[&](auto& dfs,int v)->void{
        ord[v]=cur++;
        low[v]=v;
        path.push_back(v);
        for(auto& to:g[v]){
            if(ord[to]==-1){
                dfs(dfs,to);
                par[to]=v;
                if(ord[low[to]]<ord[low[v]]){
                    low[v]=low[to];
                }
            }
            else if(ord[to]<ord[low[v]])low[v]=to;
        }
    };
    ord[s]=0;
    dfs(dfs,t);
    if(SZ(path)!=n-1)return {};
    path.erase(path.begin());
    
    const bool plus=1,minus=0;
    vector<int> sign(n);
    LinkedList<int> LL;
    vector<LinkedList<int>::Node*> nodes(n);
    nodes[s]=LL.insert_front(nullptr,s);
    nodes[t]=LL.insert_back(nodes[s],t);
    
    for(auto& v:path){
        if(sign[low[v]]==minus){
            nodes[v]=LL.insert_front(nodes[par[v]],v);
            sign[par[v]]=plus;
        }
        else{
            nodes[v]=LL.insert_back(nodes[par[v]],v);
            sign[par[v]]=minus;
        }
    }
    auto perm=LL.dump(); // index:vertices
    vector<int> ret(n);
    rep(i,0,n)ret[perm[i]]=i;

    // check
    vector<int> FROM(n),TO(n);
    FROM[s]=TO[t]=1;
    for(auto& v:perm){
        if(!FROM[v])return {};
        for(auto& to:g[v])if(ret[v]<ret[to]){
            FROM[to]=1;
        }
    }
    reverse(ALL(perm));
    for(auto& v:perm){
        if(!TO[v])return {};
        for(auto& to:g[v])if(ret[v]>ret[to]){
            TO[to]=1;
        }
    }

    return ret;
}

/**
 * @brief Bipolar Orientation
 */

Back to top page