第11章　グラフのおはなし

UnionFind.cpp

class UnionFind {
private:
        //parには親ノードの番号を格納する。その集合の根にあたるノードにはその集合の要素数*(-1)が入る(こうすることでpar[i]が負であるならばそのノードが根であることがわかる)
        vector<long long> par;
public:
        //初期化するときは全てのノードが要素数1の集合であるとする
        UnionFind(int N) { par = vector<long long>(N, -1LL); }
        int find(int x);
        long long size(int x);
        void unite(int x, int y);
        bool same(int x, int y);
};

//x番目のノードが属する集合の根を探す
int UnionFind::find(int x) {
        //もしpar[x]が負ならx番目のノードは根なのでxを返す
        if (par[x] < 0) return x;

        //そうでないならx番目のノードの親についても同じことをしながらpar[x]を更新していく
        else return par[x] = find(par[x]);
}

long long UnionFind::size(int x) {
        return -par[find(x)];
}

void UnionFind::unite(int x, int y) {
        //既に同じ集合に属しているならば繋げない
        if (same(x,y)) return;

        x = find(x);
        y = find(y);

        //大きい方に小さい方をくっ付ける
        if (size(x) < size(y)) swap(x, y);
        par[x] += par[y];
        par[y] = x;
}

bool UnionFind::same(int x, int y) {
        x = find(x);
        y = find(y);
        return x == y;
}

Kruskal.cpp

//(重み,(始点,終点))
typedef pair<long long, pair<int, int>> edge;

class Kruskal {
private:
        UnionFind *uf;
        //辺の集合
        vector<edge> e;
public:
        //mstに最小全域木を構成する辺をぶちこむ
        vector<edge> mst;
        Kruskal(int N) { uf = new UnionFind(N); }
        void add(int x, int y, long long z);
        void run();
};

void Kruskal::add(int x, int y, long long z) {
        e.push_back({ z,{x,y} });
}

void Kruskal::run() {
        sort(e.begin(), e.end());
        for (auto x : e) {
                //もし既に連結なら
                if (uf->same(x.second.first, x.second.second)) {
                        //スルーして
                        continue;
                }
                //そうでないなら
                else {
                        //最小全域木にこの辺を追加して
                        mst.push_back(x);
                        //2地点をくっつける
                        uf->unite(x.second.first, x.second.second);
                }
        }
}

Dijkstra.cpp

#define INF 1e9+7

typedef struct {
        //私は誰ですか?
        int I;
        //どこからきたか。経路復元用
        int from;
        int cost;
        //行き先,重み
        vector<pair<int,int>> to;
} _node;

bool operator > (const _node& a,const _node& b) {
        return a.cost > b.cost;
}

class Dijkstra {
private:
        priority_queue<_node,vector<_node>,greater<_node>> pque;
public:
        vector<_node> node;

        //要素数nで初期化
        Dijkstra(int n) {
                node = vector<_node>(n);
                for (int i = 0;i < n;i++) {
                        node[i].I = i;
                        node[i].from = i;
                        //はじめはcost無限大に設定
                        node[i].cost = INF;
                }
        }

        //辺を追加
        void add(int start,int end,int cost);

        //実行。firstCostは開始時のコスト
        void dijkstra(int s,int firstCost = 0);
};

void Dijkstra::add(int start,int end,int cost) {
        node[start].to.push_back({end,cost});
}

void Dijkstra::dijkstra(int s,int firstCost = 0) {
        //スタート地点のコストを設定
        node[s].cost = firstCost;

        //開始地点から到達可能な頂点をpriority_queueに入れる
        for (int i = 0;i < node[s].to.size();i++) {
                node[node[s].to[i].first].cost = node[s].to[i].second + node[s].cost;
                node[node[s].to[i].first].from = s;
                pque.push(node[node[s].to[i].first]);
        }

        //prioriry_queueが空だったら探索終了
        while (!pque.empty()) {
                //更新候補
                _node next = pque.top();
                pque.pop();

                //既にもっと小さいコストが確定しているならばスキップ
                if (next.cost > node[next.I].cost) continue;

                //更新を確定し、新たに行けるようになった頂点の更新候補をpriority_queueに入れる
                for (int i = 0;i < next.to.size();i++) {
                        if (node[next.to[i].first].cost > next.cost + next.to[i].second) {
                                node[next.to[i].first].cost = next.cost + next.to[i].second;
                                node[next.to[i].first].from = next.I;
                                pque.push(node[next.to[i].first]);
                        }
                }
        }
}

Bellman-Ford.cpp

#define INF 1e9+7;

typedef struct {
    int from;
    int to;
    int cost;
} Edge;

class BellemanFord {
private:
    vector<Edge> edge;
public:
    vector<int> dist;

    BellemanFord(int n) {
        //初めは全ての頂点のコストがINFであるとする
        dist = vector<int>(n,INF);
    }

    void add(int from,int to,int cost) {
        edge.push_back({from,to,cost});
    }

    bool bellemanford(int s,int n,int firstCost = 0) {
        dist[s] = firstCost;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < edge.size();j++) {
                //もしその辺を使ってコストを減らせるなら
                if (dist[edge[j].from] + edge[j].cost < dist[edge[j].to]) {
                        //コストを更新
                    dist[edge[j].to] = dist[edge[j].from] + edge[j].cost;
                    //もしn回目にも更新があったら負閉路が存在
                    if (i == n - 1) {
                        return true;
                    }
                }
            }
        }
        //もしreturnしていなければ負閉路は存在しない
        return false;
    }
};

Warshall_Floyd.cpp

#define INF 1e9+7

class Warshall_Floyd {
public:
        vector<vector<int>> d;

        void Warshall_Floyd(int n) {
                //ある頂点からある頂点はn^2通りある。初期化時はコスト無限大として良い
                d = vector<vector<int>>(n,vector<int>(n,INF));
        }

        void add(int s,int e,int cost) {
                d[s][e] = cost;
        }

        bool warshall_floyd() {
                for (int k = 0;k < n;k++) {
                        for (int i = 0;i < n;i++) {
                                for (int j = 0;j < n;j++) {
                                        //k経由でi->j
                                        d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
                                }
                        }
                }
        }
}

Ford_Fulkerson.cpp

struct edge {
        int to,cap,rev;
};

//MAX_Vは頂点数
vector<edge> G(MAX_V);
bool used[MAX_V];//使用済みフラグ

void add_edge(int from, int to, int cap) {
        //こう書くことでeの逆辺がG[e.to][e.rev]になる
        G[from].push_back({to, cap, G[to].size()});
        G[to].push_back({from, 0, G[from].size() - 1});
}

int dfs(int v, int t, int f) {
        if (v == t) return f;
        used[v] = true;
        for (int i = 0; i < G[v].size(); i++) {
                //次に考える辺
                edge &e = G[v][i];

                //使用済みでないかつキャパがある
                if (!used[e.to] && e.cap > 0) {
                        int d = dfs(e.to, t, min(f, e.cap));
                        //もし流せるなら
                        if (d > 0) {
                                //流して
                                e.cap -= d;
                                //逆辺の許容量が増える
                                G[e.to][e.rev].cap += d;
                                return d;
                        }
                }
        }
        return 0;
}

int max_flow(int s, int t) {
        int flow = 0;
        for (;;) {
                //使用済みフラグの初期化
                memset(used, 0, sizeof(used));

                //どれだけ流せるか
                int f = dfs(s, t, INF);

                //流せなくなったらその時点での流量の和を返す
                if (f == 0) return flow;

                //各回で流せた量をflowに足す
                flow += f;
        }
}