題目鏈接：https://vjudge.net/article/371?tdsourcetag=s_pcqq_aiomsg
題目：給定一個連通圖，題目說，任意兩個點至少有一條路線可以相互到達，
為保證任意兩點有完全不同的路線（點可以相同，邊不能相同）可以相互到達至少需要加幾條邊，
思路：tarjan縮點，之后重構圖，找出度數為1的scc個數scc_cnt，這些點相互連接，答案可以得出是 (scc_cnt+1)/2，
兩組樣例：
n = 5 ,m = 4 | （1 2） （1 3） ）（1 4） （1 5）
n = 8, m = 9 | （1 2） （1 4） （2 3） （3 4） （4 5） （5 6） （6 7） （5 8） （7 8 ）
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N = (int)5e3+10; int head[N],dfn[N],low[N],scc_no[N],s[N],du[N]; int n,m,tot,tim,scc,top; struct node{ int to; int nxt; }e[N << 2]; inline void add(int u,int v){ e[tot].to = v; e[tot].nxt = head[u]; head[u] = tot++; } void tarjan(int now,int pre){ dfn[now] = low[now] = ++tim; s[top++] = now; //這里有情況，兩點之間可能>1條路直接連接 //所以，需要處理下邊的重復問題 int to,pre_cnt = 0; for(int o = head[now]; ~o; o = e[o].nxt){ to = e[o].to; //只是一條無向邊，處理一下 if(to == pre && pre_cnt == 0){ pre_cnt = 1; continue; } if(!dfn[to]){ tarjan(to,now); low[now] = min(low[now],low[to]); } else low[now] = min(low[now],dfn[to]); } if(dfn[now] == low[now]){ ++scc; int x; do{ x = s[--top]; scc_no[x] = scc; }while(now != x); } } void rebuild(){ int to; for(int now = 1; now <= n; ++now){ for(int o = head[now]; ~o; o = e[o].nxt){ to = e[o].to; if(scc_no[now] != scc_no[to]){ ++du[scc_no[now]]; ++du[scc_no[to]]; } } } } void solve(){ int p = 0; // cout << scc << endl; //度數為什么是2的，因為是無向圖，其實除2就是度數為1了 for(int i = 1; i <= scc; ++i) if(du[i] == 2) ++p; // cout << p << endl; printf("%d\n",(p+1)/2); } int main(){ int u,v; scanf("%d%d",&n,&m); for(int i = 1;i <= n; ++i) head[i] = -1; for(int i = 0; i < m; ++i){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } tarjan(1,1); rebuild(); solve(); return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/109107.html
標籤：其他
上一篇：玩玩24點（中）