题目链接：点击打开链接
题意：
给定n个点m条边的无向图
问图中是否存在 有且仅有一个简单环和一些树，且这些树的root都在这个简单环上。
瞎写了个点双。。==
#include
#include
#include
#include
#include
#include
#include
using namespace std; #define N 105 #define M 100005 #define inf 10000000 struct Edge{ int from,to,next; }edge[2*M]; int head[N],edgenum; int Low[N],DFN[N],Stack[N];//Belong数组的值是1~block int Index,top; int Belong[N],block;//新图的连通块标号（1~block） bool Instack[N]; int bridge; //割桥数量 vector
bcc[N]; void addedge(int u,int v){ Edge E={u,v,head[u]}; edge[edgenum]=E; head[u] = edgenum++; Edge E2={v,u,head[v]};edge[edgenum]=E2;head[v] = edgenum++; } void Tarjan(int u,int pre){ int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u]; ~i ;i = edge[i].next){ v = edge[i].to; // 如果重边有效的话下面这句改成: if(v == pre && pre_num == 0){pre_num++;continue;} pre_num在for上面定义 int pre_num=0; if( v == pre )continue; if( !DFN[v] ){ Tarjan(v,u); if(Low[u] > Low[v])Low[u] = Low[v]; if(Low[v] > Low[u]) bridge++; } else if(Instack[v] && Low[u] > DFN[v])Low[u] = DFN[v]; } if(Low[u] == DFN[u]){ block++; bcc[block].clear(); do{ v = Stack[--top]; Instack[v] = false; Belong[v] = block; bcc[block].push_back(v); }while( v != u ); } } void work(int l, int r){ memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); Index = top = block = bridge = 0; for(int i = l; i <= r; i++)if(!DFN[i])Tarjan(i,i); } vector
G[N]; void suodian(){ for(int i = 1; i <= block; i++)G[i].clear(); for(int i = 0; i < edgenum; i+=2){ int u = Belong[edge[i].from], v = Belong[edge[i].to]; if(u==v)continue; G[u].push_back(v), G[v].push_back(u); } } void init(){edgenum = 0; memset(head,-1,sizeof(head));} int n, m, vis[N], siz[N], f[N]; int find(int x){return x==f[x]?x:f[x]=find(f[x]);} void Union(int x, int y){ int fx = find(x), fy = find(y); if(fx==fy)return; if(fx>fy)swap(fx,fy); f[fx] = fy; } bool dfs(int u){ vis[u] = 1; bool ok = true; for(int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if(vis[v])continue; if(bcc[v].size()>1)ok = false; if(dfs(v)==false)ok = false; } return ok; } set
myset; bool solve(){ int i, u, v; init(); for(i = 1; i <= n; i++)f[i] = i; while(m--){ scanf("%d %d",&u,&v); addedge(u, v); Union(u,v); } myset.clear(); for(i = 1; i<= n; i++)myset.insert(find(i)); if(myset.size()>1)return false; work(1, n); suodian(); memset(vis, 0, sizeof vis); memset(siz, 0, sizeof siz); for(i = 0; i < edgenum; i+=2) siz[u]+= (Belong[edge[i].from]==Belong[edge[i].to]); for(i = 1; i <= block; i++) if(!vis[i] && bcc[i].size()>1 && bcc[i].size()==siz[i] && G[i].size()>=3) if(dfs(i))return true; return false; } int main(){ while(~scanf("%d %d", &n, &m)) solve() ? puts("FHTAGN!") : puts("NO"); return 0; } /* 6 6 1 2 2 3 3 1 4 5 5 6 6 4 */