# 題目: UVa 315 - Network
# 題目說明
給一個點皆連通的無向圖
求 割點(Articulation Points
的數量
割點定義:
- 對於
root
,如果root
有兩顆以上的subtree
,那root
為割點 - 對於非
leaf
的其他節點,其child
沒有一條back edge
指到ancester
,則該點為割點
INPUT:
每筆測資第一行有一個整數 N
,代表有 N
個節點
當 N = 0
時結束程式
接下來有最多 N
行,每行有數個整數
例如 5 1 2 3 4
代表有四個邊 (5, 1)、(5, 2)、(5, 3)、(5, 4)
OUTPUT:
輸出 Articulation Points
的數量。
# 解題方法
先建圖 (為無向圖,所以建雙邊)
之後跑 dfs
,紀錄每個點的 dfn值
及 low值
如果一節點滿足以下則為割點
- 下一點的
low值
大於等於此點的dfn值
root
有兩個child
或不為root
# 參考程式碼
#include <iostream> | |
#include <vector> | |
#include <string> | |
#include <sstream> | |
using namespace std; | |
vector< vector<int> > edge; | |
vector<int> dfn, low; | |
int result, dep; | |
void dfs(int cur, int par) | |
{ | |
bool cut = false; | |
int child = 0; | |
dfn[cur] = low[cur] = ++dep; | |
for (auto& i : edge[cur]) { | |
if (!dfn[i]) { | |
++child; | |
dfs(i, cur); | |
low[cur] = min(low[cur], low[i]); | |
if (low[i] >= dfn[cur]) cut = true; | |
} | |
else if (i != par) low[cur] = min(low[cur], dfn[i]); | |
} | |
if ((child >= 2 || par != -1) && cut) ++result; | |
} | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
cout.tie(nullptr); | |
int N; | |
while (cin >> N && N) { | |
cin.ignore(); | |
result = 0, dep = 0; | |
edge.assign(N + 1, vector<int>()); | |
dfn.assign(N + 1, 0); | |
low.assign(N + 1, 0); | |
string str; | |
while (getline(cin, str)) { | |
stringstream ss(str); | |
int u, v; | |
ss >> u; | |
if (!u) break; | |
while (ss >> v) edge[v].emplace_back(u), edge[u].emplace_back(v); | |
} | |
dfs(1, -1); | |
cout << result << "\n"; | |
} | |
return 0; | |
} |
# 參考資料
https://www.larrysprognotes.com/UVa%20-%20315/