1535?深海探險 題目來源：? CodeForces 基準時間限制：1?秒 空間限制：131072?KB 分值:?40? 難度：4級算法題

很久很久以前的一天，一位美男子來到海邊，海上狂風大作。美男子希望在海中找到美人魚，但是很不幸他只找到了章魚怪。

?

然而，在世界的另一端，人們正在積極的收集怪物的行為信息，以便研制出強大的武器來對付章魚怪。由于地震的多發(fā)，以及惡劣的天氣，使得我們的衛(wèi)星不能很好的定位怪物，從而不能很好的命中目標。第一次射擊的分析結(jié)果會反映在一張由n個點和m條邊組成的無向圖上?，F(xiàn)在讓我們來確定這張圖是不是可以被認為是章魚怪。

?

為了簡單起見，我們假設章魚怪的形狀是這樣，他有一個球形的身體，然后有很多觸須連接在他的身上。可以表現(xiàn)為一張無向圖，在圖中可以被認為由三棵或者更多的樹（代表觸須）組成，這些樹的根在圖中處在一個環(huán)中（這個環(huán)代表球形身體）。

?

題目保證，在圖中沒有重復的邊，也沒有自環(huán)。

Input 單組測試數(shù)據(jù) 第一行給出兩個數(shù)，n表示圖中的點的個數(shù)，m表示圖中邊的數(shù)量。?（1≤?n≤100,0≤?m≤?n*(n-1)/2?） 接下來m行給出邊的信息， 每一行有兩上數(shù)x,y??(1≤?x,y≤?n,x≠y) 表示點x和點y之間有邊相連。每一對點最多有一條邊相連，點自身不會有邊到自己。 Output 共一行，如果給定的圖被認為是章魚怪則輸出"FHTAGN!"(沒有引號)，否則輸出"NO"(沒有引號)。 Input示例 6?6 6?3 6?4 5?1 2?5 1?4 5?4 Output示例 FHTAGN!

思路：

1、通過仔細讀題我們能夠知道，這個題就是在讓你判斷一個無向圖，是否只包含一個環(huán)&&是一個連通圖。

2、那么對于連通圖的判定以及環(huán)的個數(shù)的判定，我們其實都可以通過并查集來搞定。一開始無腦想著去Dfs.而且點數(shù)也不多，細心想想其實不必要Dfs.我們并查集直接判斷即可。

對于兩個點，如果其在一個集合中了已經(jīng)，那么這個邊一定是成環(huán)邊，對于成環(huán)邊的個數(shù)進行判定，只有這種邊的個數(shù)為1的時候，并且他是一個連通圖的時候，才能判斷他是一條章魚。

Ac代碼：

#include<stdio.h> #include<string.h> using namespace std; int f[1005]; int find(int a) {int r=a;while(f[r]!=r)r=f[r];int i=a;int j;while(i!=r){j=f[i];f[i]=r;i=j;}return r; } int merge(int a,int b) {int A,B;A=find(a);B=find(b);if(A!=B){f[B]=A;} } int main() {int n,m;while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;i++)f[i]=i;int cont=0;for(int i=0;i<m;i++){int x,y;scanf("%d%d",&x,&y);if(find(x)==find(y)){cont++;}else merge(x,y);}int root=0;for(int i=1;i<=n;i++){if(f[i]==i)root++;}if(root==1&&cont==1){printf("FHTAGN!\n");}else printf("NO\n");} }

總結(jié)

以上是生活随笔為你收集整理的51nod 1535 深海探险【思维+并查集】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。