graph class

graph.cpp

template<typename T> struct Edge
{
  int src, dst; T w;
  Edge() {};
  Edge(int src, int dst): src(src), dst(dst) {w=1;}
  Edge(int src, int dst, T w): src(src), dst(dst), w(w){}
  bool operator<(const Edge &e)const{return w != e.w ? w > e.w : (src != e.src ? src < e.src : dst < e.dst);}
  bool operator==(const Edge &e){return src == e.src && dst == e.dst;}
};

template<typename T> class Graph : public vector<vector<Edge<T>>>
{
private:
  pair<T,int> farthest(int p, int v)
  {
    pair<T,int> r(0,v);
    for(auto e : (*this)[v]) if(e.dst != p)
    {
      auto t = farthest(v,e.dst);
      t.first += e.w;
      if(t.first > r.first) r=t;
    }
    return r;
  }

  void backward(Graph &h, int v, int s, int r,
  vector<int> &no, vector<vector<int>> &cmp,
  vector<int> &prev, vector<vector<int>> &next, vector<T> &mcost,
  vector<int> &mark, T &cost, bool &found)
  {
    const int n = h.size();
    if(mark[v])
    {
      vector<int> tmp = no;
      found = true;
      do {
        cost += mcost[v];
        v = prev[v];
        if (v != s)
        {
          while (cmp[v].size() > 0)
          {
            no[cmp[v].back()] = s;
            cmp[s].push_back(cmp[v].back());
            cmp[v].pop_back();
          }
        }
      } while (v != s);
      for(auto j : cmp[s]) if(j!=r) for(int l=0;l<h[j].size();l++)
        if(no[h[j][l].src]!=s) h[j][l].w -= mcost[tmp[j]];
    }
    mark[v] = true;
    for(auto i : next[v]) if(no[i]!=no[v]&&prev[no[i]]==v)
      if (!mark[no[i]]||i==s)
        backward(h,i,s,r,no,cmp,prev,next,mcost,mark,cost,found);
  }

  void subaps(int current, int prev, int &timer,
  vector<bool> &visited, vector<int> &prenum,
  vector<int> &parent, vector<int> &lowest)
  {
    prenum[current]=lowest[current]=timer++;
    visited[current]=true;
    for(auto e : (*this)[current])
    {
      int next = e.dst;
      if(!visited[next])
      {
        parent[next]=current;
        subaps(next,current,timer,visited,prenum,parent,lowest);
        lowest[current]=min(lowest[current],lowest[next]);
      }
      else if(next != prev)
        lowest[current]=min(lowest[current],prenum[next]);
    }
  }

  void subbrs(int current, int prev, int &timer,
  vector<int>&prenum, vector<int>&lowest, set<Edge<T>>&bridges)
  {
    prenum[current]=lowest[current]=timer++;
    for(auto e : (*this)[current]) if(e.dst!=prev)
    {
      if(prenum[e.dst]==-1)
      {
        subbrs(e.dst,current,timer,prenum,lowest,bridges);
        lowest[current]=min(lowest[current],lowest[e.dst]);
        if(prenum[current] < lowest[e.dst])
          bridges.insert(Edge<T>(min(e.dst,e.src),max(e.dst,e.src)));
      }
      lowest[current]=min(lowest[current],prenum[e.dst]);
    }
  }

public:
  T inf;
  Graph(int n){(*this).resize(n);inf=numeric_limits<T>::max();}
  void direct(int s, int t){(*this)[s].push_back(Edge<T>(s,t));}
  void direct(int s, int t, T w){(*this)[s].push_back(Edge<T>(s,t,w));}
  void undirect(int s, int t){direct(s,t);direct(t,s);}
  void undirect(int s, int t, T w){direct(s,t,w);direct(t,s,w);}

  /*
    cost : O(|V|)
  */
  T diameter(void)
  {
    auto r = farthest(-1,0);
    auto t = farthest(-1,r.second);
    return t.first;
  }

  /*
    s : start point
    cost : O(|E|+|V|log(|V|))
    dist : distances
  */
  vector<T> dijkstra(int s = 0)
  {
    const int n = (*this).size();
    priority_queue<Edge<T>> PQ;
    vector<T> dist(n,inf);
    dist[s] = 0; Edge<T> e(-1,s,0);
    PQ.push(e);
    while(!PQ.empty())
    {
      auto f = PQ.top(); PQ.pop();
      int u = f.dst;
      if(dist[u] < f.w * (-1)) continue;
      for(int j=0;j<(*this)[u].size();j++)
      {
        int v = (*this)[u][j].dst;
        if(dist[v] > dist[u] + (*this)[u][j].w)
        {
          dist[v] = dist[u] + (*this)[u][j].w;
          Edge<T> e(-1,v,dist[v]*(-1));
          PQ.push(e);
        }
      }
    }
    return dist;
  }

  /*
    s : start point
    cost : O(|V||E|)
    first : is negative cycle ?
    second : distances
  */
  pair<bool,vector<T>> bellmanFord(int s = 0)
  {
    const int n = (*this).size();
    vector<T> dist(n,inf);
    dist[s] = 0;
    for(int i=0;i<n;i++)
    {
      bool update = false;
      for(int v=0;v<n;v++) for(auto e : (*this)[v])
      {
        if (dist[v] != inf && dist[e.dst] > dist[v] + e.w)
        {
          dist[e.dst] = dist[v] + e.w;
          update = true;
          if(i==n-1) return make_pair(true,dist);
        }
      }
      if(!update) break;
    }
    return make_pair(false,dist);
  }

  /*
    Minimum Spanning Tree (Prim's algorithm)
    r : root
    cost : O(|E|+|V|log|V|) (because priority_queue use paring sort)
    first : total cost
    second : edges
  */
  pair<T, vector<Edge<T>>> MST(int r = 0)
  {
    const int n = (*this).size();
    vector<Edge<T>> U;
    T total = 0;
    vector<bool> visited(n,false);
    priority_queue<Edge<T>> Q;
    Q.push(Edge<T>(-1,r,0));
    while (!Q.empty())
    {
      auto e = Q.top(); Q.pop();
      if (visited[e.dst]) continue;
      U.push_back(e);
      total += e.w;
      visited[e.dst] = true;
      for(auto f : (*this)[e.dst]) if (!visited[f.dst]) Q.push(f);
    }
    return make_pair(total, U);
  }

  /*
    Minimum Spanning Arborescence(Chu-Liu/Edmond)
    r : root
    cost : O(|V||E|)
  */
  T MSA(int r = 0) {
    const int n = (*this).size();
    Graph<T> h(n);
    for(int i=0;i<n;i++) for(auto e : (*this)[i]) h[e.dst].push_back(e);
    vector<int> no(n);
    vector< vector<int> > cmp(n);
    for(int i=0;i<n;i++) cmp[i].push_back(no[i]=i);
    for (T cost=0;;)
    {
      vector<int> prev(n,-1);
      vector<T> mcost(n,inf);
      for(int j=0;j<n;j++) if(j!=r) for(auto e : h[j])
        if (no[e.src] != no[j])
          if (e.w < mcost[no[j]])
            mcost[no[j]] = e.w, prev[no[j]] = no[e.src];
      vector<vector<int>> next(n);
      for(int i=0;i<n;i++) if(prev[i]>=0)
        next[prev[i]].push_back(i);
      bool stop = true;
      vector<int> mark(n);
      for(int i=0;i<n;i++) if(i!=r&&!mark[i]&&!cmp[i].empty())
      {
        bool found = false;
        backward(h, i, i, r, no, cmp, prev, next, mcost, mark, cost, found);
        if (found) stop = false;
      }
      if (stop)
      {
        for(int i=0;i<n;i++) if(prev[i] >= 0) cost+=mcost[i];
        return cost;
      }
    }
  }

  /*
    articulation points
    costs O(|E|log|V|)
  */
  set<int> APs(void)
  {
    const int n = (*this).size();
    set<int> ap;
    if(n==1) return ap;
    int timer = 1;
    vector<bool> visited(n,false);
    vector<int> prenum(n), parent(n), lowest(n);
    subaps(0,-1,timer,visited,prenum,parent,lowest);
    int np = 0;
    for(int i=1; i<n; i++)
    {
      int p = parent[i];
      if(p==0) np++;
      else if(prenum[p]<=lowest[i]) ap.insert(p);
    }
    if(np > 1) ap.insert(0);
    return ap;
  }

  /*
    bridges
    only undirect graph
  */
  set<Edge<T>> bridges(void)
  {
    const int n = (*this).size();
    set<Edge<T>> bridges;
    vector<int> prenum(n,-1), lowest(n,inf);
    int timer = 0;
    for(int i=0;i<n;i++) if(prenum[i]==-1)
      subbrs(i,-1,timer,prenum,lowest,bridges);
    return bridges;
  }
};