題：
給定 N 個節點和 M 個邊的無向圖。你需要解決2個問題：
- 問題 1：對于每條邊 j (j : 1 -> M)，如果洗掉該邊，請計算無法相互到達的節點數（這 2 個節點之間沒有路徑）。
- 問題 2：對于每個節點 i (i : 1 -> N)，如果洗掉該節點（也洗掉了與其相連的所有邊），請計算彼此無法到達的節點數。
例子：
N = 6, M = 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4
（邊被描述為 u - v）
結果：
- 對于每條邊 j (j : 1 -> M): 0 0 0 9 0 0 0
- 對于每個節點 i (i : 1 -> N): 0 0 6 6 0 0
P/S：我想了很多天，但找不到這個問題的正確答案
uj5u.com熱心網友回復：
如果初始圖是連通的，那么第一個問題是搜索橋梁，第二個問題是搜索切割頂點/關節點。
顯示橋接后得到連接組件的大小（有兩個），需要的結果是大小的乘積（例如，大小為 2 的組件和大小為 3 的組件給出 6 對）
顯示切割頂點后，組件數量可能更大，結果是大小的成對乘積之和（對于大小為 1,2,3 的組件，結果為1*2 1*3 2*3=11對）
可以在此處找到使用 DFS 解決這兩個問題的 C 代碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/321834.html