51Nod 1535 思维+DFS

xiaoxiao2021-02-28  6

51Nod 1535


思路: 根据图的性质,一定是在一棵树的基础上有一个环,故边的条数一定等于点的数目。

然后再DFS判断一下是否连通即可。


代码:

#include<cmath> #include<string> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int A = 100 + 10; class Gra{ public: int v,next; }G[A*A*2]; int head[A],tot,n,m; bool vis[A]; void add(int u,int v){ G[tot].v = v; G[tot].next = head[u]; head[u] = tot++; } void dfs(int u,int pre){ vis[u] = true; for(int i=head[u] ;i!=-1 ;i=G[i].next){ int v = G[i].v; if(v == pre || vis[v]) continue; dfs(v,u); } } bool check(){ if(n != m) return false; memset(vis,0,sizeof(vis)); bool flag = false; for(int i=1 ;i<=n ;i++){ if(!vis[i]){ if(flag) return false; flag = true; dfs(i,0); } } return true; } int main(){ scanf("%d%d",&n,&m); memset(head,-1,sizeof(head));tot = 0; for(int i=1 ;i<=m ;i++){ int u,v;scanf("%d%d",&u,&v); add(u,v);add(v,u); } if(check()) puts("FHTAGN!"); else puts("NO"); return 0; }
转载请注明原文地址: https://www.6miu.com/read-1100141.html

最新回复(0)