51Nod - 1535 图论基础 + 搜索环

题意：

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

然而，在世界的另一端，人们正在积极的收集怪物的行为信息，以便研制出强大的武器来对付章鱼怪。由于地震的多发，以及恶劣的天气，使得我们的卫星不能很好的定位怪物，从而不能很好的命中目标。第一次射击的分析结果会反映在一张由n个点和m条边组成的无向图上。现在让我们来确定这张图是不是可以被认为是章鱼怪。

为了简单起见，我们假设章鱼怪的形状是这样，他有一个球形的身体，然后有很多触须连接在他的身上。可以表现为一张无向图，在图中可以被认为由三棵或者更多的树（代表触须）组成，这些树的根在图中处在一个环中（这个环代表球形身体）。

题目保证，在图中没有重复的边，也没有自环。

单组测试数据第一行给出两个数，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 66 36 45 12 51 45 4Output示例
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;}