很久很久以前的一天,一位美男子來到海邊,海上狂風(fēng)大作。美男子希望在海中找到美人魚,但是很不幸他只找到了章魚怪。
?
然而,在世界的另一端,人們正在積極的收集怪物的行為信息,以便研制出強(qiáng)大的武器來對(duì)付章魚怪。由于地震的多發(fā),以及惡劣的天氣,使得我們的衛(wèi)星不能很好的定位怪物,從而不能很好的命中目標(biāo)。第一次射擊的分析結(jié)果會(huì)反映在一張由n個(gè)點(diǎn)和m條邊組成的無向圖上?,F(xiàn)在讓我們來確定這張圖是不是可以被認(rèn)為是章魚怪。
?
為了簡單起見,我們假設(shè)章魚怪的形狀是這樣,他有一個(gè)球形的身體,然后有很多觸須連接在他的身上??梢员憩F(xiàn)為一張無向圖,在圖中可以被認(rèn)為由三棵或者更多的樹(代表觸須)組成,這些樹的根在圖中處在一個(gè)環(huán)中(這個(gè)環(huán)代表球形身體)。
?
題目保證,在圖中沒有重復(fù)的邊,也沒有自環(huán)。
單組測(cè)試數(shù)據(jù) 第一行給出兩個(gè)數(shù),n表示圖中的點(diǎn)的個(gè)數(shù),m表示圖中邊的數(shù)量。?(1≤?n≤100,0≤?m≤?n*(n-1)/2?) 接下來m行給出邊的信息, 每一行有兩上數(shù)x,y??(1≤?x,y≤?n,x≠y) 表示點(diǎn)x和點(diǎn)y之間有邊相連。每一對(duì)點(diǎn)最多有一條邊相連,點(diǎn)自身不會(huì)有邊到自己。
共一行,如果給定的圖被認(rèn)為是章魚怪則輸出"FHTAGN!"(沒有引號(hào)),否則輸出"NO"(沒有引號(hào))。
6?6 6?3 6?4 5?1 2?5 1?4 5?4
FHTAGN!
?允許其他 AC 的用戶查看此代碼,分享代碼才能查看別人的代碼并有機(jī)會(huì)獲得勛章
因?yàn)轭}中說明沒有重邊和自環(huán),并且能組成章魚怪的話該無向圖中一定有且只有一個(gè)環(huán),并且題中說明
章魚怪的觸須是有以環(huán)中某些點(diǎn)為根的樹組成,因此可以得出結(jié)論,只要點(diǎn)數(shù)等于邊數(shù)就能組成章魚怪。
但是有一個(gè)坑點(diǎn),就是給你的圖并非是一個(gè)連通圖,因此并查集或者搜索判斷一發(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