SHARE
TWEET

Untitled

a guest Oct 21st, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <unordered_map>
  5.  
  6. using namespace std;
  7.  
  8. struct vertex
  9. {
  10.     vector<int> neighbours;
  11.     vector<int> results;
  12.     bool visited = 0;
  13. };
  14.  
  15. bool ifEdge(vector<vertex>& g, int v, int w)
  16. {
  17.     if (find(g[v].neighbours.begin(), g[v].neighbours.end(), 0) != g[v].neighbours.end())
  18.         return true;
  19.     else
  20.         return false;
  21. }
  22.  
  23. void input(vector<vertex>& g)
  24. {
  25.     int n, m;
  26.     cin >> n >> m;
  27.  
  28.     g.assign(n + 1, vertex());
  29.  
  30.     for (int i = 0; i < m; i++)
  31.     {
  32.         int a, b;
  33.         cin >> a >> b;
  34.  
  35.         g[a].neighbours.push_back(b);
  36.         g[b].neighbours.push_back(a);
  37.     }
  38. }
  39.  
  40. bool solve(vector<vertex>& g, vector<vector<int>>& r, int s, int v)
  41. {
  42.     if (r[v][s] != -1)
  43.         return r[v][s];
  44.  
  45.     if (s == 0)
  46.         return r[v][s] = ifEdge(g, v, 0);
  47.  
  48.     for (int i = 0; i < g[v].neighbours.size(); i++)
  49.         if (ifEdge(g, v, g[v].neighbours[i]) && solve(g, r, s - 1 << g[v].neighbours[i], g[v].neighbours[i]))
  50.             return r[v][s] = true;
  51.    
  52.     return r[v][s] = false;
  53. }
  54.  
  55. int main()
  56. {
  57.     int z;
  58.     cin >> z;
  59.  
  60.     while (z--)
  61.     {
  62.         vector<vertex> graph;
  63.         vector<vector<int>> results;
  64.         int s;
  65.  
  66.         input(graph);
  67.  
  68.         s = 1 << (graph.size() + 1);
  69.         results.assign(graph.size(), vector<int>(s + 1, -1));
  70.  
  71.         solve(graph, results, s - 1, 0);
  72.  
  73.         if (results[0][s - 1])
  74.             cout << "TAK" << endl;
  75.         else
  76.             cout << "NIE" << endl;
  77.     }
  78.    
  79.     return 0;
  80. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top