1535深海探险
题目来源：CodeForces
基准时间限制：1秒 空间限制：131072KB 分值:40难度：4级算法题
很久很久以前的一天，一位美男子来到海边，海上狂风大作。美男子希望在海中找到美人鱼，但是很不幸他只找到了章鱼怪。
然而，在世界的另一端，人们正在积极的收集怪物的行为信息，以便研制出强大的武器来对付章鱼怪。由于地震的多发，以及恶劣的天气，使得我们的卫星不能很好的定位怪物，从而不能很好的命中目标。第一次射击的分析结果会反映在一张由n个点和m条边组成的无向图上。现在让我们来确定这张图是不是可以被认为是章鱼怪。
为了简单起见，我们假设章鱼怪的形状是这样，他有一个球形的身体，然后有很多触须连接在他的身上。可以表现为一张无向图，在图中可以被认为由三棵或者更多的树（代表触须）组成，这些树的根在图中处在一个环中（这个环代表球形身体）。
题目保证，在图中没有重复的边，也没有自环。
Input
单组测试数据 第一行给出两个数，n表示图中的点的个数，m表示图中边的数量。（1≤n≤100,0≤m≤n*(n-1)/2） 接下来m行给出边的信息， 每一行有两上数x,y(1≤x,y≤n,x≠y) 表示点x和点y之间有边相连。每一对点最多有一条边相连，点自身不会有边到自己。
Output
共一行，如果给定的图被认为是章鱼怪则输出"FHTAGN!"(没有引号)，否则输出"NO"(没有引号)。
Input示例
66
63
64
51
25
14
54
Output示例
FHTAGN!
//只需要判断是不是只有一个环的连通图即可，tarjan瞎搞搞
1 # include <cstdio> 2 # include <cstring> 3 # include <cstdlib> 4 # include <iostream> 5 # include <vector> 6 # include <queue> 7 # include <stack> 8 # include <map> 9 # include <bitset>10 # include <sstream>11 # include <set>12 # include <cmath>13 # include <algorithm>14 # pragma comment(linker,"/STACK:102400000,102400000")15 using namespace std;16 # define LLlong long17 # define prpair18 # define mkp make_pair19 # define lowbit(x) ((x)&(-x))20 # define PIacos(-1.0)21 # define INF 0x3f3f3f3f3f3f3f3f22 # define eps 1e-823 # define MOD 100000000724 25 inline int scan() {26int x=0,f=1; char ch=getchar();27while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}28while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}29return x*f;30 }31 inline void Out(int a) {32if(a<0) {putchar('-'); a=-a;}33if(a>=10) Out(a/10);34putchar(a%10+'0');35 }36 # define MX 10537 /**************************/38 39 int n,m;40 int ccc,cir;41 vector<int> G[MX];42 int inst[MX];43 int vis[MX];44 45 void func(int x,int pre)46 {47vis[x]=ccc;48inst[x]=1;49for (int i=0;i<G[x].size();i++)50{51 if (G[x][i]==pre) continue;52 53 if (!vis[G[x][i]])54 func(G[x][i],x);55 else56 {57 if (inst[G[x][i]])58 cir++;59 }60}61inst[x]=0;62 }63 64 int main()65 {66while (scanf("%d%d",&n,&m)!=EOF)67{68 for (int i=1;i<=m;i++)69 {70 int x,y;71 scanf("%d%d",&x,&y);72 G[x].push_back(y);73 G[y].push_back(x);74 }75 ccc=0;76 cir=0;77 memset(vis,0,sizeof(vis));78 for (int i=1;i<=n;i++)79 {80 if (!vis[i])81 {82 ccc++;83 memset(inst,0,sizeof(inst));84 func(i,-1);85 }86 }87 if (ccc==1&&cir==1)88 printf("FHTAGN!\n");89 else printf("NO\n");90}91return 0;92 }
View Code
