SCC (Sstrongly Connected Components)
(graph/scc.hpp)

• View this file on GitHub
• Last update: 2022-07-07 14:50:02+09:00
• Include: #include "graph/scc.hpp"

• 有向グラフを強連結成分分解する
• $O(E + V)$

ポイント

• DFSして、帰りがけに頂点番号をつける
  • 上流のほうが下流よりも番号が大きい
• 逆グラフで頂点の大きい順にDFSする。
  • DAGのトポロジカルソート順の順番なので、逆グラフではDAGの下流には影響しない。
• 同じ連結成分に属するのであれば一回のDFSで辿れるはず。

Depends on

• graph/graphTemplate.hpp

Verified with

• test/graph/scc.aoj_GRL_3_C.test.cpp

Code

#pragma once
#include <algorithm>
#include <unordered_map>
#include <vector>

#include "graph/graphTemplate.hpp"
using namespace std;

template <typename T = int>
struct SCC {
public:
  int n;
  Graph<T> G;
  vector<int> component;
  SCC(Graph<T> &_G) {
    n = _G.size();
    G = _G;
    build();
  }

  void build() {
    rG = Graph(n);
    for(size_t i =0;i<n;i++){
      for(auto &e: G[i]) {
        rG.add_directed_edge(e.to, e.from, e.cost);
      }
    }
    component.assign(n, -1);
    used.assign(n, false);
    for (size_t v = 0; v < n; v++)
      if (!used[v]) dfs(v);
    reverse(order.begin(), order.end());
    int k = 0;
    for (auto v : order)
      if (component[v] == -1) rdfs(v, k), k++;
  }

  bool is_same(int u, int v) { return component[u] == component[v]; }

  long long count_pair() {
    unordered_map<int, long long> value_counts;
    for (int k : component) {
      value_counts[k]++;
    }
    long long ans = 0;
    for (auto x : value_counts) {
      ans += x.second * (x.second - 1) / 2;
    }
    return ans;
  }

private:
  Graph<T> rG;
  vector<int> order;
  vector<bool> used;

  void dfs(int v) {
    used[v] = 1;
    for (auto nv : G[v]) {
      if (!used[nv]) dfs(nv);
    }
    order.push_back(v);
  }

  void rdfs(int v, int k) {
    component[v] = k;
    for (auto nv : rG[v]) {
      if (component[nv] < 0) rdfs(nv, k);
    }
  }
};

#line 2 "graph/scc.hpp"
#include <algorithm>
#include <unordered_map>
#include <vector>

#line 3 "graph/graphTemplate.hpp"
#include <iostream>
using namespace std;

template <typename T = int>
struct Edge {
  int from, to;
  T cost;
  int idx;
  Edge() = default;

  Edge(int from, int to, T cost = 1, int idx = -1)
      : from(from), to(to), cost(cost), idx(idx) {}
  operator int() const { return to; }
};

template <typename T = int>
struct Graph {
  vector<vector<Edge<T>>> g;
  int es;

  Graph() = default;
  explicit Graph(int n) : g(n), es(0) {}

  size_t size() const { return g.size(); }

  void add_directed_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es++);
  }

  void add_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es);
    g[to].emplace_back(to, from, cost, es++);
  }
  void read(int M, int padding = -1, bool weighted = false,
            bool directed = false) {
    for (int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      a += padding;
      b += padding;
      T c = T(1);
      if (weighted) {
        cin >> c;
      }
      if (directed) {
        add_directed_edge(a, b, c);
      } else {
        add_edge(a, b, c);
      }
    }
  }
  inline vector<Edge<T>> &operator[](const int &k) { return g[k]; }

  inline const vector<Edge<T>> &operator[](const int &k) const { return g[k]; }
};

template <typename T>
using Edges = vector<Edge<T>>;
#line 7 "graph/scc.hpp"
using namespace std;

template <typename T = int>
struct SCC {
public:
  int n;
  Graph<T> G;
  vector<int> component;
  SCC(Graph<T> &_G) {
    n = _G.size();
    G = _G;
    build();
  }

  void build() {
    rG = Graph(n);
    for(size_t i =0;i<n;i++){
      for(auto &e: G[i]) {
        rG.add_directed_edge(e.to, e.from, e.cost);
      }
    }
    component.assign(n, -1);
    used.assign(n, false);
    for (size_t v = 0; v < n; v++)
      if (!used[v]) dfs(v);
    reverse(order.begin(), order.end());
    int k = 0;
    for (auto v : order)
      if (component[v] == -1) rdfs(v, k), k++;
  }

  bool is_same(int u, int v) { return component[u] == component[v]; }

  long long count_pair() {
    unordered_map<int, long long> value_counts;
    for (int k : component) {
      value_counts[k]++;
    }
    long long ans = 0;
    for (auto x : value_counts) {
      ans += x.second * (x.second - 1) / 2;
    }
    return ans;
  }

private:
  Graph<T> rG;
  vector<int> order;
  vector<bool> used;

  void dfs(int v) {
    used[v] = 1;
    for (auto nv : G[v]) {
      if (!used[nv]) dfs(nv);
    }
    order.push_back(v);
  }

  void rdfs(int v, int k) {
    component[v] = k;
    for (auto nv : rG[v]) {
      if (component[nv] < 0) rdfs(nv, k);
    }
  }
};

Back to top page