APP
?收藏
?關(guān)注
很久很久以前的一天，一位美男子來到海邊，海上狂風(fēng)大作。美男子希望在海中找到美人魚，但是很不幸他只找到了章魚怪。
?
然而，在世界的另一端，人們正在積極的收集怪物的行為信息，以便研制出強(qiáng)大的武器來對付章魚怪。由于地震的多發(fā)，以及惡劣的天氣，使得我們的衛(wèi)星不能很好的定位怪物，從而不能很好的命中目標(biāo)。第一次射擊的分析結(jié)果會反映在一張由n個點和m條邊組成的無向圖上。現(xiàn)在讓我們來確定這張圖是不是可以被認(rèn)為是章魚怪。
?
為了簡單起見，我們假設(shè)章魚怪的形狀是這樣，他有一個球形的身體，然后有很多觸須連接在他的身上。可以表現(xiàn)為一張無向圖，在圖中可以被認(rèn)為由三棵或者更多的樹（代表觸須）組成，這些樹的根在圖中處在一個環(huán)中（這個環(huán)代表球形身體）。
?
題目保證，在圖中沒有重復(fù)的邊，也沒有自環(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
共一行，如果給定的圖被認(rèn)為是章魚怪則輸出"FHTAGN!"(沒有引號)，否則輸出"NO"(沒有引號)。
Input示例
6?6 6?3 6?4 5?1 2?5 1?4 5?4
Output示例
FHTAGN!
System?Message?
(題目提供者)
Visual?C++的運行時限為：1000?ms ，空間限制為：131072?KB?
示例及語言說明請按這里
?允許其他 AC 的用戶查看此代碼，分享代碼才能查看別人的代碼并有機(jī)會獲得勛章
因為題中說明沒有重邊和自環(huán)，并且能組成章魚怪的話該無向圖中一定有且只有一個環(huán)，并且題中說明
章魚怪的觸須是有以環(huán)中某些點為根的樹組成，因此可以得出結(jié)論，只要點數(shù)等于邊數(shù)就能組成章魚怪。
但是有一個坑點，就是給你的圖并非是一個連通圖，因此并查集或者搜索判斷一發(fā)就OK了。
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<functional>
using namespace std;
#define ll long long
#define inf 1000000000
#define mod 1000000007
#define maxn 208
#define lowbit(x) (x&-x)
#define eps 1e-9
vector<int>q[maxn];
bool used[maxn];
int p[maxn];
int find(int x)
{
if(p[x]==x)
return x;
return p[x]=find(p[x]);
}
int main(void)
{
bool flag=0;
int n,m,i,j,x,y;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
p[i]=i;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
int t1=find(x),t2=find(y);
if(t1!=t2)
p[t1]=t2;
}
for(i=1;i<=n;i++)
if(find(p[i])!=find(p[1]))
{
flag=1;
break;
}
if(m==n && flag==0)
printf("FHTAGN!
");
else
printf("NO
");
return 0;
}本文摘自 ：https://blog.51cto.com/u
