Advertisement
999ms

Untitled

Apr 8th, 2020
340
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.06 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define endl "\n"
  5. vector <vector <int>> g;
  6. vector <int> color;
  7. vector <int> pr;
  8. int Start = -1;
  9. int End = -1;
  10.  
  11. bool dfs(int v, int p)
  12. {
  13.     color[v] = 1;
  14.     for (auto to : g[v])
  15.     {
  16.         if (to == p)
  17.             continue;
  18.         if (color[to] == 1)
  19.         {
  20.             Start = to;
  21.             End = v;
  22.             return true;
  23.         }
  24.         if (color[to] == 0)
  25.         {
  26.             pr[to] = v;
  27.             if (dfs(to,v))
  28.                 return true;
  29.         }
  30.     }
  31.     color[v] = 2;
  32.     return false;
  33. }
  34.  
  35. struct SNM
  36. {
  37.     vector<list<int>> ar;
  38.     vector<int> pr;
  39.     SNM(int n)
  40.     {
  41.         ar.resize(n);
  42.         pr.resize(n);
  43.         for(int i = 0; i < n; i++)
  44.         {
  45.             pr[i] = i;
  46.             ar[i].push_back(i);
  47.         }
  48.     }
  49.     void Merge(int a, int b)
  50.     {
  51.         a = pr[a];
  52.         b = pr[b];
  53.         if(ar[b].size() < ar[a].size())
  54.             swap(a,b);
  55.         if(a == b)
  56.             return;
  57.         for(int tmp : ar[a])
  58.         {
  59.             ar[b].push_back(tmp);
  60.             pr[tmp] = b;
  61.         }
  62.     }
  63.     int Get(int i)
  64.     {
  65.         return pr[i];
  66.     }
  67. };
  68.  
  69. int main()
  70. {
  71.     ios_base::sync_with_stdio(false);
  72.     cin.tie(nullptr);
  73.     cout.tie(nullptr);
  74.     int n,m;
  75.     cin>>n>>m;
  76.     g.resize(n);
  77.     color.assign(n,0);
  78.     pr.assign(n,-1);
  79.     for (int i = 0; i < m; i++)
  80.     {
  81.         int x,y;
  82.         cin>>x>>y;
  83.         x--,y--;
  84.         g[x].push_back(y);
  85.         g[y].push_back(x);
  86.     }
  87.     bool fl = false;
  88.     for (int i = 0; i < n && !fl; i++)
  89.     {
  90.         if (color[i] != 0)
  91.             continue;
  92.         fl = dfs(i, -1);
  93.         if (fl)
  94.             break;
  95.     }
  96.     if (!fl)
  97.     {
  98.         cout<<"NO"<<endl;
  99.         return 0;
  100.     }
  101.     vector <int> circle;
  102.     circle.push_back(Start);
  103.     int myEnd = End;
  104.     while(Start != End)
  105.     {
  106.         circle.push_back(End);
  107.         End = pr[End];
  108.     }
  109.     End = myEnd;
  110.     for (int i = 0; i < g[Start].size(); i++) {
  111.         if (g[Start][i] == End)
  112.         {
  113.             swap(g[Start][i], g[Start].back());
  114.             g[Start].pop_back();
  115.             break;
  116.         }
  117.     }
  118.     for (int i = 0; i < g[End].size(); i++) {
  119.         if (g[End][i] == Start)
  120.         {
  121.             swap(g[End][i], g[End].back());
  122.             g[End].pop_back();
  123.             break;
  124.         }
  125.     }
  126.     fl = false;
  127.     color.assign(n,0);
  128.     for (int i = 0; i < n; i++)
  129.     {
  130.         if (color[i] != 0)
  131.             continue;
  132.         fl = dfs(i, -1);
  133.         if (fl)
  134.             break;
  135.     }
  136.     if (fl)
  137.     {
  138.         cout<<"NO"<<endl;
  139.         return 0;
  140.     }
  141.     SNM snm(n);
  142.  
  143.     for (int i = 0; i < n; i++)
  144.     {
  145.         for (int j = 1; j < g[i].size(); j++)
  146.         {
  147.             snm.Merge(g[i][j], g[i][j-1]);
  148.         }
  149.     }
  150.     set<int> st;
  151.     for (int i = 0; i < n; i++)
  152.     {
  153.         st.insert(snm.Get(i));
  154.     }
  155.     if (circle.size() < 3 || n != m)
  156.         cout<<"NO"<<endl;
  157.     else
  158.         cout<<"FHTAGN!"<<endl;
  159.  
  160. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement