src/graph/strongly_connected_components.hpp

View this file on GitHub
Last update: 2022-12-19 02:10:28+09:00
Include: #include "src/graph/strongly_connected_components.hpp"

Depends on

src/graph/template.hpp

Verified with

test/aoj/grl_3_c.test.cpp

Code

#pragma once

#include <bits/stdc++.h>
using namespace std;

#include "./template.hpp"

struct StronglyConnectedComponents {
private:
  int n;
  Graph<> graph;
  Graph<> r_graph;
  vector<bool> used;
  vector<int> order, comp;

public:
  StronglyConnectedComponents(int n)
      : n(n), graph(n), r_graph(n), used(n, false), comp(n, -1) {}

  void add_edge(int u, int v) {
    graph[u].emplace_back(u, v);
    r_graph[v].emplace_back(v, u);
  }

  void build() {
    for (int i = 0; i < n; ++i) {
      if (!used[i]) {
        dfs(i);
      }
    }
    int cnt = 0;
    reverse(order.begin(), order.end());
    for (int i : order) {
      if (comp[i] == -1) {
        r_dfs(i, cnt++);
      }
    }
  }

  int operator[](int k) { return comp[k]; }

private:
  void dfs(int idx) {
    used[idx] = true;
    for (auto edge : graph[idx]) {
      if (!used[edge.to]) {
        dfs(edge.to);
      }
    }
    order.push_back(idx);
  }
  void r_dfs(int idx, int cnt) {
    comp[idx] = cnt;
    for (auto edge : r_graph[idx]) {
      if (comp[edge.to] == -1) {
        r_dfs(edge.to, cnt);
      }
    }
  }
};

#line 2 "src/graph/strongly_connected_components.hpp"

#include <bits/stdc++.h>
using namespace std;

#line 2 "src/graph/template.hpp"

#line 4 "src/graph/template.hpp"
using namespace std;

template <typename T = long long> struct Edge {
  int from, to;
  T cost;
  Edge(int from, int to, T cost = 1) : from(from), to(to), cost(cost) {}
};

template <typename T = long long> using Edges = vector<Edge<T>>;
template <typename T = long long> using Graph = vector<Edges<T>>;

template <typename T = long long> using Matrix = vector<vector<T>>;
#line 7 "src/graph/strongly_connected_components.hpp"

struct StronglyConnectedComponents {
private:
  int n;
  Graph<> graph;
  Graph<> r_graph;
  vector<bool> used;
  vector<int> order, comp;

public:
  StronglyConnectedComponents(int n)
      : n(n), graph(n), r_graph(n), used(n, false), comp(n, -1) {}

  void add_edge(int u, int v) {
    graph[u].emplace_back(u, v);
    r_graph[v].emplace_back(v, u);
  }

  void build() {
    for (int i = 0; i < n; ++i) {
      if (!used[i]) {
        dfs(i);
      }
    }
    int cnt = 0;
    reverse(order.begin(), order.end());
    for (int i : order) {
      if (comp[i] == -1) {
        r_dfs(i, cnt++);
      }
    }
  }

  int operator[](int k) { return comp[k]; }

private:
  void dfs(int idx) {
    used[idx] = true;
    for (auto edge : graph[idx]) {
      if (!used[edge.to]) {
        dfs(edge.to);
      }
    }
    order.push_back(idx);
  }
  void r_dfs(int idx, int cnt) {
    comp[idx] = cnt;
    for (auto edge : r_graph[idx]) {
      if (comp[edge.to] == -1) {
        r_dfs(edge.to, cnt);
      }
    }
  }
};