题意：
很久很久以前的一天，一位美男子来到海边，海上狂风大作。美男子希望在海中找到美人鱼，但是很不幸他只找到了章鱼怪。
然而，在世界的另一端，人们正在积极的收集怪物的行为信息，以便研制出强大的武器来对付章鱼怪。由于地震的多发，以及恶劣的天气，使得我们的卫星不能很好的定位怪物，从而不能很好的命中目标。第一次射击的分析结果会反映在一张由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示例
6 6
6 3
6 4
5 1
2 5
1 4
5 4
Output示例
FHTAGN!
思路：
按照题目要求一步一步来，首先这图中一定有且只有一个长度不小于3的环，所以需要dfs搜索找到环，并且将环中的节点保存下来。这里我是利用一个deep数组来储存每个节点在dfs树中的深度，一开始deep都初始化成0，第一个遍历的根节点deep是1，然后子节点依次+1，当前节点的所有子节点都递归结束的时候，当前节点的deep值变回0，当到达一个新的节点并且新的节点deep值不为0的时候，说明这里存在一个环，而组成环的节点就是deep值在当前节点u已经由的deep[u]和又一次对其赋值的k+1之间。
当找到一个环的时候，剩下的就是要判断以环上的每个点遍历下去是否是一棵树，这里要注意，要先将环上的边都删掉，然后将环上的所有节点的访问标记vis都设成true。这样，当dfs过程中遇到了vis为true的情况，则说明存在另外的环，输出“NO"。
vis的另外的作用就是判断图是否连通。如果有节点的vis在判断完环上所有节点之后还是false，那说明图不连通。
代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int n, m;
bool G[MAXN][MAXN], vis[MAXN];
int deep[MAXN];
vector <int> cir;
int l, r;
bool cmp(const int x, const int y) {
return deep[x] < deep[y];
}
bool dfs(int u, int pre, int k) {
deep[u] = k;
vis[u] = true;
for (int v = 1; v <= n; v++) {
if (!G[u][v] || v == pre) continue;
if (vis[v]) {
l = deep[v]; r = k + 1;
return true;
}
if (dfs(v, u, k + 1)) return true;
}
deep[u] = 0;
return false;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u][v] = G[v][u] = true;
}
if (!dfs(1, -1, 1)) {
puts("NO");
return 0;
}
for (int i = 1; i <= n; i++) {
if (deep[i] >= l && deep[i] <= r) {
cir.push_back(i);
// printf("%d ", i);
}
}
if (cir.size() < 3) {
puts("NO");
return 0;
}
sort(cir.begin(), cir.end(), cmp);
int cnt = cir.size();
for (int i = 0; i < cnt - 1; i++)
G[cir[i]][cir[i + 1]] = G[cir[i + 1]][cir[i]] = false;
G[cir[0]][cir[cnt - 1]] = G[cir[cnt - 1]][cir[0]] = false;
memset(deep, 0, sizeof(deep));
memset(vis, false, sizeof(vis));
for (int i = 0; i < cnt; i++)
vis[cir[i]] = true;
for (int i = 0; i < cnt; i++) {
if (dfs(cir[i], -1, 1)) {
puts("NO");
return 0;
}
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
puts("NO");
return 0;
}
}
puts("FHTAGN!");
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-660164.html
