初めに

今回グラフ、木とかなり大きなテーマとなってます。頑張りましょう...

そもそもグラフ、木を知っていますか？グラフとは頂点と辺によって構成されるデータ構造で、木はグラフの中で連結かつ閉路が存在しないものです。n頂点の場合、辺がn-1本になるのは分かりますね。

1. グラフの表現方法

隣接リスト

リスト(実装しやすさからvectorを利用)で実装

一例

typedef pair<int, int> P;

vector<int> to[10000];
// 辺に重みがある時
vector<P> to[10000]; // 辺に重みがある時
// P(to, weight)とする
// もちろんstruct作るのもいい(そっちのほうが可読性ありそう)

vectorのvectorは遅いって聞いたので使ってない(初期化面倒なイメージがある) もちろん2重vectorでもいいよ

隣接行列

グラフを行列で表現

一例

constexp int INF = 1<<30; // 仮想的な無限大 問題によって変える必要あるかも
int d[100][100]; // a→bに辺が存在: 1 / 存在しない: 0
// 重み付きの時
int d[100][100]; // a→bに辺が存在: weight / 存在しない: INF

2. グラフ上のdfs

基本ですね。

例) 二部グラフ(2色で塗って両端が同じ色の辺が存在しないグラフ)か判定しろ

vector<int> to[10000]; // 隣接リスト

int color[10000]; // 0: まだ, 1: 白, -1: 黒, 0で初期化
bool dfs(int i, int col) { // trueなら2部グラフでは無い
	if (color[i] == col) return false;
	if (color[i] == -col) return true; // 2部グラフでない
	color[i] = col;
	for (int x : to[i]) {
		if (dfs(x, -col)) return true;
	}
	return false;
}

bool solve() { // 二部グラフか？
	for (int i = 0; i < n; i++) if (color[i] == 0) {
		if (dfs(i, 1)) {
			return false;
		}
	}
	return true;
}

グラフのdfsより木のdfsの方がよくみる(何故なら木はどのような順番でdfsしても結果は一意な為)

木のdfsはABC-Dくらいでよく出る。テンプレ

int dfs(int i, int par) {
	for (int x : to[i]) if (x != par) {
		// 処理
		dfs(x, i);
	}
	// 処理
}

// 0が根, 根に親は存在しないのでありえない-1を入れておく
dfs(0, -1);

とし、親情報を持つ。(親が誰か分からないと無限ループになるので)

3. グラフの最短経路問題

Dijkstra法

一始点全終点

最も近いものから順に結果を決めていく。負の辺がある時は不可能

Bellman-ford法

一始点全終点

負の経路がある時用。負の閉路判定もできる。

Warshall-floyd

全始点全終点

int d[100][100]; // 辺が無い時はINF

for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
	d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

ライブラリ(いずれ改良します)

template <typename T>
class Graph {
  struct edge { ll to; T cost; };
  struct edge_data { ll from, to; T cost; };

  ll v;
  vector<vector<edge>> e, re;
  vector<edge_data> ed;
  vector<bool> used;
  vector<ll> vs, cmp;
  bool isDirected, isMinasEdge;
public:
  Graph(ll _v, bool _isDirected = true, ll range_add = 0) {
    // range_add 0:no / 1:in / 2:out / 3:in+out
    //_v++;
    v = _v, isDirected = _isDirected; isMinasEdge = false;
    e.resize(v), re.resize(v);
  }
  void add_edge(ll s, ll t, T cost = 1) {
    e[s].push_back((edge){t, cost});
    if (!isDirected) e[t].push_back((edge){s, cost});
    else re[t].push_back((edge){s, cost});
    ed.push_back((edge_data){s, t, cost});
    if (cost < 0) isMinasEdge = true;
  }
  vector<T> dijkstra(ll s) {
    vector<T> d(v, INF);
    d[s] = 0;
    auto edge_cmp = [](const edge& a, const edge& b) { return a.cost > b.cost; };
    priority_queue<edge, vector<edge>, decltype(edge_cmp)> pq(edge_cmp);
    pq.push((edge){s, 0});
    while (!pq.empty()) {
      edge temp = pq.top(); pq.pop();
      if (d[temp.to] < temp.cost) continue;
      for (const edge& next : e[temp.to]) {
        T cost = temp.cost + next.cost;
        if (d[next.to] > cost) {
          d[next.to] = cost;
          pq.push((edge){next.to, cost});
        }
      }
    }
    return d;
  }
  vector<T> bellmanford(ll s) {
    vector<T> d(v, INF);
    d[s] = 0;
    for (ll i = 0; i < v; i++) {
      for (const edge_data& temp : ed) {
        if (d[temp.from] != INF && d[temp.to] > d[temp.from] + temp.cost) d[temp.to] = d[temp.from] + temp.cost;
        if (!isDirected && d[temp.to] != INF && d[temp.from] > d[temp.to] + temp.cost) d[temp.from] = d[temp.to] + temp.cost;
      }
    }
    for (ll i = 0; i < v; i++) {
      for (const edge_data& temp : ed) {
        if (d[temp.from] != INF && d[temp.to] > d[temp.from] + temp.cost) d[temp.to] = -INF;
        if (!isDirected && d[temp.to] != INF && d[temp.from] > d[temp.to] + temp.cost) d[temp.from] = -INF;
      }
    }
    return d;
  }
  vector<T> shortest_path(ll s) {
    if (isMinasEdge) return bellmanford(s);
    else return dijkstra(s);
  }
  T kruskal() {
    // if (isDirected)
    UnionFind uf(v);
    auto edge_data_cmp = [](const edge_data& a, const edge_data& b) { return a.cost < b.cost; };
    sort(ed.begin(), ed.end(), edge_data_cmp);
    T ans = 0;
    for (const edge_data& temp : ed) {
      if (uf.isSame(temp.from, temp.to)) continue;
      uf.merge(temp.from, temp.to);
      ans += temp.cost;
    }
    return ans;
  }
  void scc_dfs(ll s) {
    used[s] = true;
    for (const edge& i : e[s]) if (!used[i.to]) scc_dfs(i.to);
    vs.push_back(s);
  }
  void scc_rdfs(ll s, ll k) {
    used[s] = true;
    cmp[s] = k;
    for (const edge& i : re[s]) if (!used[i.to]) scc_rdfs(i.to, k);
  }
  vector<ll> scc() {
    used.resize(v);
    fill(used.begin(), used.end(), false);
    cmp.resize(v);
    vs.clear();
    for (ll i = 0; i < v; i++) if (!used[i]) scc_dfs(i);
    used.resize(v);
    fill(used.begin(), used.end(), false);
    ll k = 0;
    for (ll i = vs.size() - 1; i >= 0; i--) if (!used[vs[i]]) scc_rdfs(vs[i], k++);
    return cmp;
  }
};

4. 最小全域木

グラフの部分グラフで、全域的な木の内辺の重みの総和が最小のもの

Kruscal法 辺の重さの小さい順に選び、閉路ができない時だけつなぐ　Union Findで判定

5. 強連結成分分解

閉路を潰すしてDAGにします。DAGにするとDPができたり、2-SATって問題が解けたり応用が広いです。やることは2回DFSやるだけなんですが。