---
# System prepended metadata

title: 計算圖形的 low 與 dfn 值

---

計算圖形的 low 與 dfn 值
===
```
#include <iostream>
#include <algorithm>
#include<vector>
using namespace std;
int dfn[1000], low[1000],n=0;
vector<vector<int>> br;
vector<bool> has;
void init(int h) { //初始化
    int i;
    for (i = 0; i < h; i++) {
        dfn[i] = low[i] = -1;
    }
}
void dfs(int x,int f) {
    dfn[x] = low[x] = n++;
    for (auto i : br[x]) {
        if (i == f) { continue; }
        if (dfn[i] == -1) {
            dfs(i, x);
            low[x] = min(low[x], low[i]);
        }
        else {
            low[x] = min(low[x], dfn[i]);
        }
    }
}
int main() {
    int u, v, mx = -1;
    br.resize(1000);//限制容量為最大值
    while (cin >> u >> v) {
        br[u].push_back(v);
        br[v].push_back(u);
        mx = max({ mx, u, v });
    }
    init(mx + 1);
    for (int i = 3; i < mx + 1; i++) {
        if (dfn[i] == -1) {
            dfs(i, i);
        }
    }
    for (int i = 0; i < 3; i++) {
        if (dfn[i] == -1) {
            dfs(i, i);
        }
    }
    cout << "    ";
    for (int i = 0; i < n; i++) {
        cout << i << " \n"[i == n - 1];
    }
    cout << "dfn ";
    for (int i = 0; i < n; i++) {
        cout << dfn[i] << " \n"[i == n - 1];
    }
    cout << "low ";
    for (int i = 0; i < n; i++) {
        cout << low[i] << " \n"[i == n - 1];
    }
    return 0;
}
```