問題 C: PK沒有女朋友
時間限制: 1 Sec 內存限制: 128 MB

[提交][狀態][討論版]
題目描述
因為 PK 上個月沒有去師范看她女朋友，所以 PK 的女朋友最近又不理他了。異地戀實在是太辛苦了，理工到師范的距
離，對于他來說，就像是駐馬店到廣州的距離。
曾有詩這樣寫道：

世上最遙遠的距離，不是生與死的距離，不是天各一方，而是我就站在你面前，你卻不知道我愛你。

PK 決定要送給他的女朋友一條項鏈，希望能挽回女朋友的心，但他長期打 ACM 已經分辨不出什么是項鏈了，所以想請
你幫幫他。
在PK 眼中，他所買的東西就是個 n個點和 m 條邊構成的無向圖（……）。判斷這個圖是不是項鏈，我們要做以下三
件事情：

• 首先我們要在圖上找一個環。而且我們要保證在圖上只能找到這一個環。
• 環上可以長出一些樹，這些樹的根都在環上。樹應該由至少一個節點組成，但為了美觀起見，應該要能找到至少 3 棵
  樹。
• 重邊和自環是不允許出現的。不然女孩子有可能不小心把頭伸進里面，然后出不來……
  換句話說合格的圖應該保證只有一個環，可以組成至少3棵樹，沒有重邊和自環。
  如果滿足以上三個條件， PK 就會非常高興，并大叫一聲 Bingo。否則，他的女朋友就會和他分手……

輸入
第一行，給出 n, m (1 ≤ n ≤ 100, 0 ≤ m ≤ 10^5 ）

接下來m行，每一行有兩個整數 ui，vi（1<=ui,vi<=n ),表示ui,vi之間有邊相連 。可能存在重邊和自環 .

輸出
如果是項鏈則輸出 Bingo，否則輸出 Break up。
樣例輸入

6 6 6 3 6 4 5 1 2 5 1 4 5 4

樣例輸出

Bingo

提示
/*
本題會可以出一個結論：
要存在一個三元以上的環，沒有自環，并且所有點都連通，那么點數要等于邊數

不連通，點數不等于邊數

本題要求沒有重邊，且沒有自環，即如圖所示情況：

那么本題可以在輸入邊的時候判斷有沒有重邊和自環。
之后再看點數n是否等于邊m，如果都滿足條件，再來一遍dfs判斷所有的點是否連通。
*/
ac_code:

#include <bits/stdc++.h> using namespace std; vector<int>mp[105]; bool link[105][105]; bool vis[105]; void dfs(int s) {int iSize = mp[s].size();for(int i = 0; i < iSize; i++){int to = mp[s][i];if(!vis[to]){vis[to] = true;dfs(to);}}return; } int main() {int n,m;scanf("%d%d",&n,&m);int u,v,flag = 1;for(int i = 0; i < m; i++){scanf("%d%d",&u,&v);if(!link[u][v]&&!link[v][u]){mp[u].push_back(v);mp[v].push_back(u);link[u][v] = true;//link[v][u] = true;}else{flag = 0;}}if(!flag||n!=m){puts("Break up");return 0;}else{dfs(1);for(int i = 1; i <= n; i++){if(!vis[i]){puts("Break up");return 0;}}}puts("Bingo");return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的问题 C: PK没有女朋友（判断是否存在1个三元环，dfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

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