---
# System prepended metadata

title: Graph Algorithms

---

# Graph Algorithms

## [Counting Rooms](https://cses.fi/problemset/task/1192)

有兩種解法。一個是用union find來連兩個一樣的，但是不是完全最優。另一種解法是flood fill。
從左上角遍歷，每當我們跑到空氣時，就跑一個bfs把空氣填滿，然後答案加一。

:::spoiler
```cpp=
#include <iostream>
#include <bits/stdc++.h>
const int MOD = 1e9+7;
using ll = long long;
using namespace std;
int dir[] = {0,1,0,-1,0};
void bfs(vector<vector<char>>& grid,int iroot,int jroot) {
    int n = grid.size();
    int m = grid[0].size();
 
    queue<pair<int,int>> que;
    que.emplace(iroot,jroot);
    grid[iroot][jroot] = '#';
    while (!que.empty()) {
        auto [i,j] = que.front();
        que.pop();
 
        for (int d=0;d<4;d++) {
            int inext = i + dir[d], jnext = j + dir[d+1];
            if (inext == -1 || jnext == -1 || inext == n || jnext == m) continue;
            if (grid[inext][jnext] == '#') continue;
            grid[inext][jnext] = '#';
            que.emplace(inext,jnext);
        }
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(false);
	int n,m;
    cin >> n >> m;
    vector<vector<char>> grid(n,vector<char>(m));
 
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            cin >> grid[i][j];
        }
    }
    int ans = 0;
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (grid[i][j] != '.') continue;
            bfs(grid,i,j);
            ans++;
        }
    }
    cout << ans << endl;
}
```
::: 

## [Labyrinth](https://cses.fi/problemset/task/1193)

關鍵就是在bfs的每一步，都設定“對於節點`nexti, nextj`”，他是從哪裡來的，才能到最短距離。
也就是這一行
`from[ni][nj] = {i,j};`
最後看一看`from`有沒有被設定過。有的話代表有路徑，就從終點build出整個路徑，但這個路徑是反轉過的，所以反著輸出即可。

:::spoiler
```cpp!
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define maxn 4000
int dir[] = {0,1,0,-1,0};
char grid[1001][1001];
bool been[1001][1001];
pair<int,int> from[1001][1001];
 
char ans[500000];
int main() {
    cin.tie(0)->sync_with_stdio(0);
 
    int n,m;
    cin >> n >> m;
    int ai, aj, bi, bj;
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'A') ai = i, aj = j;
        }
    }
 
    queue<pair<int,int>> que;
    que.emplace(ai,aj);
    been[ai][aj]=true;
    bool found=false;
    while (!que.empty()) {
        auto [i,j] = que.front();
        que.pop();
 
        for (int d=0;d<4;d++) {
            int ni = i+dir[d], nj = j+dir[d+1];
            if (ni==-1||nj==-1||ni==n||nj==m) continue;
            if (been[ni][nj] || grid[ni][nj]=='#') continue;
            been[ni][nj] = true;
            from[ni][nj] = {i,j};
            if (grid[ni][nj]=='B') {
                found=true;
                bi = ni, bj = nj;
                break;
            }
            que.emplace(ni,nj);
        }
        if (found) break;
    }
    if (!found) cout << "NO\n", exit(0);
    cout << "YES\n";
    int ansn = 0;
    int ci = bi, cj = bj;
    while (ci != ai || cj != aj) {
        auto [nci,ncj] = from[ci][cj];
        if (nci<ci) ans[ansn]='D';
        else if (nci>ci) ans[ansn]='U';
        else if (ncj>cj) ans[ansn]='L';
        else ans[ansn]='R';
        ansn++;
        ci = nci, cj = ncj;
    }
    reverse(ans,ans+ansn);
    cout << ansn << '\n';
    for (int i=0;i<ansn;i++) cout << ans[i];
}
```
:::

## [Building Roads](https://cses.fi/problemset/task/1666)

MST 裸題。此處使用 Kruskal's algorithm.

:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct UF {
	vector<int> root, rank;
	int clus;
	UF(int n): root(n), rank(n), clus(n) {
		iota(root.begin(),root.end(),0);
	}
	void unite(int a,int b) {
		a = find(a), b = find(b);
		if (a!=b) {
			clus--;
			if (rank[a] < rank[b]) {
				root[a] = b;
			}
			else {
				root[b] = a;
				if (rank[a]==rank[b]) rank[a]++;
			}
		}
	}
	int find(int a) {
		if (root[a]==a) return a;
		return root[a] = find(root[a]);
	}
};
int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
 
	int n,m; cin >> n >> m;
	UF uf(n);
	for (int i=0;i<m;i++) {
		int a,b;
		cin >> a >> b; a--, b--;
		uf.unite(a,b);
	}
 
	vector<pair<int,int>> ans;
	for (int i=0;i<n;i++) {
		if (uf.clus==1) break;
		for (int j=i+1;j<n;j++) {
			if (uf.clus==1) break;
			if (uf.find(i)==uf.find(j)) continue;
			ans.emplace_back(i,j);
			uf.unite(i,j);
		}
	}
	cout << ans.size() << '\n';
	for (auto [a,b] : ans) {
		cout << a+1 << ' ' << b+1 << '\n';
	}
}
```
:::

## [Message Route](https://cses.fi/problemset/task/1667)

跟上上題差不多，一樣要印路徑就用一樣的手法。
不同的是我用了鏈式前向星。[那是啥？](https://blog.csdn.net/sugarbliss/article/details/86495945)

:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct {
    int to,next;
} es[400001];
int cnt = 0;
int head[100001];
void add_edge(int u,int v) {
    es[cnt].to = v;
    es[cnt].next = head[u];
    head[u] = cnt++;
}
int prevm[100001];
bool been[100001];
int ans[100001];
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
 
    int n,m;
    cin >> n >> m;
    cnt = 0;
    memset(head,-1,sizeof(head));
    for (int i=0;i<m;i++) {
        int u,v;
        cin >> u >> v, u--, v--;
        add_edge(u,v);
        add_edge(v,u);
    }
    queue<int> que;
    que.emplace(0);
 
    memset(prevm,-1,sizeof(prevm));
    been[0] = true;
    while (!que.empty()) {
        int node = que.front();
        que.pop();
 
        for (int e=head[node];e!=-1;e=es[e].next) {
            int next = es[e].to;
            if (been[next]) continue;
            been[next] = true;
            prevm[next] = node;
            que.emplace(next);
        }
    }
    if (prevm[n-1]==-1) cout << "IMPOSSIBLE\n", exit(0);
    int ansn = 0;
    int curr = n-1;
    while (curr!=-1) {
        ans[ansn++] = curr;
        curr = prevm[curr];
    }
    cout << ansn << '\n';
    for (int i=ansn-1;~i;i--) cout << ans[i]+1 << ' '; cout << '\n';
}
```
:::

## [Building Teams](https://cses.fi/problemset/task/1668)

二分圖判定模板題。dfs 每走一步就換一次顏色，可以確立這個節點的顏色。如果發現鄰邊已經被著色過，就說明不可以完成二著色。
二分圖著色可以在線性時間解決。但注意三分圖著色性判斷是np-hard。

:::spoiler
```cpp!
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int color[100001], head[100001];
int cnt = 0;
struct {
    int to,next;
} edges[400002];
void add_edge(int u,int v) {
    edges[cnt].to = v;
    edges[cnt].next = head[u];
    head[u] = cnt++;
} 
void dfs(int i,int c) {
    color[i] = c;
    for (int e=head[i];e!=-1;e=edges[e].next) {
        int ne = edges[e].to;
        if (color[ne]) {
            if (color[ne]==c) cout << "IMPOSSIBLE\n", exit(0);
            continue;
        }
        dfs(ne,c==1?2:1);
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;
    cin >> n >> m;
    memset(head,-1,sizeof(head));
    cnt = 0;
    for (int i=0;i<m;i++) {
        int a,b;
        cin >> a >> b, a--, b--;
        add_edge(a,b);
        add_edge(b,a);
    }
    memset(color,0,sizeof(color));
    for (int i=0;i<n;i++) {
        if (color[i]) continue;
        dfs(i,1);
    }
    for (int i=0;i<n;i++) cout << color[i] << ' '; cout << '\n';
}
```
:::

## [Shortest Routes I](https://cses.fi/problemset/task/1671)

Dijkstra algorithm 裸題。

:::spoiler
```cpp!
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int cnt = 0;
struct Edge {
    int to,next,w;
} edges[200001];
int head[100001];
void init() {
    cnt = 0;
    memset(head,-1,sizeof(head));
}
void add_edge(int u,int v,int w) {
    edges[cnt].to=v;
    edges[cnt].next=head[u];
    edges[cnt].w=w;
    head[u] = cnt++;
}
 
ll ans[100001];
int main() {
    cin.tie(0)->sync_with_stdio(0);
 
    int n,m;
    cin >> n >> m;
 
    init();
    for (int i=0;i<m;i++) {
        int u,v,w;
        cin >> u >> v >> w, u--, v--;
        add_edge(u,v,w);
    }
    using INFO = pair<ll,int>; // dist, node
    priority_queue<INFO,vector<INFO>,greater<INFO>> pq;
    pq.emplace(0ll,0);
    memset(ans,0x3f,sizeof(ans));
    ans[0] = 0;
    while (!pq.empty()) {
        auto [dist,node] = pq.top();
        pq.pop();
        if (dist>ans[node]) continue;
        for (int e = head[node];e!=-1;e=edges[e].next) {
            int to = edges[e].to;
            ll ndist = dist + edges[e].w;
            if (ndist>=ans[to]) continue;
            ans[to] = ndist;
            pq.emplace(ndist,to);
        }
    }
    for (int i=0;i<n;i++) cout << ans[i] << ' ';
    cout << '\n';
}
```
:::

## [Shortest Routes II](https://cses.fi/problemset/task/1672)

Floyd Warshall algorithm 裸題。

:::spoiler
```cpp!
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dist[501][501];
int main() {
    cin.tie(0)->sync_with_stdio(0);
    
	int n,m,q; 
    cin >> n >> m >> q;
    memset(dist,0x3f,sizeof(dist));
    ll INF = dist[0][0];
    for (int i=0;i<m;i++) {
        int a,b,c;
        cin >> a >> b >> c, a--, b--;
        dist[b][a] = dist[a][b] = min(dist[a][b],(ll)c);
    }
    for (int i=0;i<n;i++) dist[i][i] = 0;
    for (int k=0;k<n;k++) {
        for (int i=0;i<n;i++) {
            for (int j=0;j<n;j++) {
                if (dist[i][k]==INF || dist[k][j]==INF) continue;
                dist[j][i] = dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    for (int i=0;i<q;i++) {
        int a,b;
        cin >> a >> b, a--, b--;
        if (dist[a][b] == INF) cout << "-1\n";
        else cout << dist[a][b] << '\n';
    }
}
```
:::