鏈接：https://ac.nowcoder.com/acm/contest/392/I
來源：牛客網

華華和月月逛公園
時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 32768K，其他語言65536K
64bit IO Format: %lld
題目描述
月月和華華一起去逛公園了。公園很大，為了方便，可以抽象的看成一個N個點M條邊的無向連通圖（點是景點，邊是道路）。公園唯一的入口在1號點，月月和華華要從這里出發，并打算參觀所有的景點。因為他們感情很好，走多遠都不會覺得無聊，所以所有景點和道路都可以無數次的重復經過。月月發現，有些路可走可不走，有些路則必須要走，否則就無法參觀所有的景點。現在月月想知道，有幾條路是不一定要經過的。因為這是個很正常的公園，所以沒有重邊和自環。
輸入描述:
第一行兩個正整數N和M，表示點數和邊數。
接下來M行，每行兩個正整數U和V表示一條無向邊。
保證給定的圖是連通的。
輸出描述:
輸出一行一個非負整數表示不一定要經過的邊有幾條。
示例1
輸入
復制
5 5
1 2
2 3
3 4
4 5
3 5
輸出
復制
3
說明
例如第三條邊，月月和華華可以依次走過第一條、第二條、第五條、第四條邊走過全部的景點，所以第三條邊不一定要經過。同理還有第四條、第五條邊，答案為3。
備注:
1\le N\le 10^51≤N≤10
5
，1\le M\le 3\times10^51≤M≤3×10
5

思路：

月月發現，有些路可走可不走，有些路則必須要走，否則就無法參觀所有的景點。

無向圖中保持聯通必須走過的邊即為橋，總邊數減去橋的個數就是答案，求橋用tarjian算法即可。

細節見代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;} inline void getInt(int* p); const int maxn = 100010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ /* * 求 無向圖的割點和橋 * 可以找出割點和橋，求刪掉每個點后增加的連通塊。 * 需要注意重邊的處理，可以先用矩陣存，再轉鄰接表，或者進行判重 */ const int MAXN = maxn; const int MAXM = 10 * maxn; struct Edge {int to, next;bool cut;//是否為橋的標記 } edge[MAXM]; int head[MAXN], tot; int Low[MAXN], DFN[MAXN], Stack[MAXN]; int Index, top; bool Instack[MAXN]; bool cut[MAXN]; int add_block[MAXN];//刪除一個點后增加的連通塊 int bridge;void addedge(int u, int v) {edge[tot].to = v; edge[tot].next = head[u]; edge[tot].cut = false;head[u] = tot++; }int ans = 0;void Tarjan(int u, int pre) {int v;Low[u] = DFN[u] = ++Index;Stack[top++] = u;Instack[u] = true;int son = 0;for (int i = head[u]; i != -1; i = edge[i].next){v = edge[i].to;if (v == pre)continue;if ( !DFN[v] ){son++;Tarjan(v, u);if (Low[u] > Low[v])Low[u] = Low[v];//橋//一條無向邊(u,v)是橋，當且僅當(u,v)為樹枝邊，且滿足DFS(u)<Low(v)。if (Low[v] > DFN[u]){ans++;bridge++;edge[i].cut = true;edge[i ^ 1].cut = true;}//割點//一個頂點u是割點，當且僅當滿足(1)或(2) (1) u為樹根，且u有多于一個子樹。//(2) u不為樹根，且滿足存在(u,v)為樹枝邊(或稱父子邊，//即u為v在搜索樹中的父親)，使得DFS(u)<=Low(v)if (u != pre && Low[v] >= DFN[u]) //不是樹根{cut[u] = true;add_block[u]++;}}else if ( Low[u] > DFN[v])Low[u] = DFN[v];}//樹根，分支數大于1if (u == pre && son > 1)cut[u] = true;if (u == pre)add_block[u] = son - 1;Instack[u] = false;top--; }int n, m; void solve(int N) {memset(DFN, 0, sizeof(DFN));memset(Instack, false, sizeof(Instack));memset(add_block, 0, sizeof(add_block));memset(cut, false, sizeof(cut));Index = top = 0;bridge = 0;for (int i = 1; i <= N; i++)if (!DFN[i])Tarjan(i, i);// for(int i = 1;i <= N;i++)// if(cut[i])// ans++;printf("%d\n", m - ans); } void init() {tot = 0;memset(head, -1, sizeof(head)); } int main() {//freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);//freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);init();gg(n);gg(m);repd(i, 1, m){int x, y;gg(x); gg(y);addedge(x, y);addedge(y, x);}solve(n);return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉載于:https://www.cnblogs.com/qieqiemin/p/11420005.html

總結

以上是生活随笔為你收集整理的牛客小白月赛12 I华华和月月逛公园 （tarjian 求桥）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。