• API
• FAQ
• Tools
• Archive
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[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.

Top