Codeforces 104C : Cthulhu

問題リンク : Problem - 104C - Codeforces

問題概要 :
無向グラフがあたえられる
このグラフに、ちょうど１つだけ閉路が存在するかどうか判定せよ

解法 :
まず、グラフが非連結な場合があるので最初にDFSやらなんやらして非連結ならNOと出力して終わる
次に、グラフの頂点のうち次数が１のものを削除する
新しくできたグラフに対してもまた同様にして次数１の頂点を削除する
この動作を次数１の頂点がなくなるまで繰り返す
この処理が終わった後のグラフが閉路になっているかどうかを判定すればよい
これは頂点の数と辺の数が一致しているかどうかで判定できる
以上
こどふぇのチーム戦で似たような問題があった気がする

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int V,E;
set<int> G[110];
bool visited[110];

void dfs(int v){
  for(set<int>::iterator it=G[v].begin();it!=G[v].end();it++){
    int dst = *it;
    if( !visited[dst] ) {
      visited[dst] = true;
      dfs(dst);
    }
  }
}

void compute(){
  memset(visited,false,sizeof(visited));
  int cnt = 0;
  rep(i,V) if( !visited[i] ) {
    visited[i] = true;
    ++cnt;
    if( cnt >= 2 ) { puts("NO"); return; }
    dfs(i);
  }
  bool update = true;
  while( update ){
    update = false;
    rep(i,V) if( G[i].size() == 1 ) {
      int next = *G[i].begin();
      G[i].erase(next);
      G[next].erase(i);
      update = true;
    }
  }
  int nV=0,nE = 0;
  rep(i,V) {
    nE += (int)G[i].size();
    if( !G[i].empty() ) ++nV;
  }
  nE >>= 1;
  puts((nV&&nV==nE)?"FHTAGN!":"NO");
}

int main(){
  cin >> V >> E;
  rep(_,E){
    int x,y;
    cin >> x >> y;
    --x, --y;
    G[x].insert(y);
    G[y].insert(x);
  }
  compute();
  return 0;
}