# 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';
}
}
```
:::
Sign in with Wallet
Connect another wallet