fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define PB push_back
  4. #define MP make_pair
  5. #define F first
  6. #define S second
  7. typedef long long ll;
  8. typedef vector<int> vi;
  9. typedef pair<int, int> pii;
  10. typedef pair<ll, ll> pll;
  11. const int INF = 1e9 + 7;
  12. const int MAXN = 2005;
  13.  
  14. int n, m, k, dd;
  15. vi G[MAXN];
  16. bool vis[MAXN];
  17. vi big;
  18.  
  19. vi ans;
  20.  
  21. void input() {
  22.         int x, y;
  23.         cin >> n >> m >> k;
  24.         for (int i = 0; i < m; i++) {
  25.                 cin >> x >> y;
  26.                 G[x].PB(y);
  27.                 G[y].PB(x);
  28.         }
  29. }
  30.  
  31. int deg(int v) {
  32.         set<int> ms;
  33.         for (int u : ans) {
  34.                 ms.insert(u);
  35.         }
  36.         if (ms.count(v)) {
  37.                 return 0;
  38.         }
  39.         int degree = 0;
  40.         for (int u : G[v]) {
  41.                 if (ms.count(u) == 0) {
  42.                         degree++;
  43.                 }
  44.         }
  45.         return degree;
  46. }
  47.  
  48. bool areDegreeGood() {
  49.         set<int> ms;
  50.         for (int u : ans) {
  51.                 ms.insert(u);
  52.         }
  53.         for (int i = 1; i <= n; i++) {
  54.                 if (ms.count(i)) {
  55.                         continue;
  56.                 }
  57.                 int degree = 0;
  58.                 for (int u : G[i]) {
  59.                         if (ms.count(u) == 0) {
  60.                                 degree++;
  61.                                 if (degree > 2) {
  62.                                         return false;
  63.                                 }
  64.                         }
  65.                 }
  66.         }
  67.         return true;
  68. }
  69.  
  70. void dfs(int v, int parent = -1) {
  71.         vis[v] = true;
  72.         for (int u : G[v]) {
  73.                 if (u == parent || vis[u]) {
  74.                         continue;
  75.                 }
  76.                 dfs(u, v);
  77.         }
  78. }
  79.  
  80. vi getCycles() {
  81.         for (int i = 1; i <= n; i++) {
  82.                 vis[i] = false;
  83.         }
  84.         for (int u : ans) {
  85.                 vis[u] = true;
  86.         }
  87.         for (int i = 1; i <= n; i++) {
  88.                 int d = deg(i);
  89.                 set<int> ms;
  90.                 for (int u : ans) {
  91.                         ms.insert(u);
  92.                 }
  93.                 if (d <= 1 && ms.count(i) == 0) {
  94.                         vis[i] = true;
  95.                         dfs(i);
  96.                 }
  97.         }
  98.  
  99.         vi onCycles;
  100.         for (int i = 1; i <= n; i++) {
  101.                 if (!vis[i]) {
  102.                         onCycles.PB(i);
  103.                         dfs(i);
  104.                 }
  105.         }
  106.  
  107.         return onCycles;
  108. }
  109.  
  110. void output() {
  111.         cout << "TAK\n";
  112.         cout << ans.size() << "\n";
  113.         for (int u : ans) {
  114.                 cout << u << " ";
  115.         }
  116.         cout << "\n";
  117.         exit(0);
  118. }
  119.  
  120. void licz(int ile) {
  121.         if (areDegreeGood()) {
  122.                 vi cycles = getCycles();
  123.                 if ((int)cycles.size() <= ile) {
  124.                         for (int u : cycles) {
  125.                                 ans.PB(u);
  126.                         }
  127.                         output();
  128.                 }
  129.         }
  130.         if (ile == 0) {
  131.                 return;
  132.         }
  133.  
  134.         for (int i: big) {
  135.                 if (deg(i) > 2) {
  136.                         ans.PB(i);
  137.                         licz(ile - 1);
  138.                         ans.pop_back();
  139.                         int possible = 3;
  140.                         set<int> ms;
  141.                         for (int u: ans) {
  142.                                                         ms.insert(u);
  143.                                                 }
  144.  
  145.                         for (int u = 0; possible; u++) {
  146.                                 ans.PB(G[i][u]);
  147.                                 licz(ile - 1);
  148.                                 ans.pop_back();
  149.                                 if (ms.count(G[i][u]) == 0) {
  150.                                                                         possible--;
  151.                                                                 }
  152.                         }
  153.                         break;
  154.                 }
  155.         }
  156. }
  157.  
  158. void solve() {
  159.         for (int i = 1; i <= n; i++) {
  160.             if (deg(i) > 2) {
  161.                 big.PB(i);
  162.             }
  163.         }
  164.         licz(k);
  165.         cout << "NIE\n";
  166. }
  167.  
  168. int main() {
  169.         ios_base::sync_with_stdio(0);
  170.         cin.tie(NULL);
  171.         cout.tie(NULL);
  172.  
  173.         input();
  174.         solve();
  175.  
  176.         return 0;
  177. }
Success #stdin #stdout 0s 15288KB
comments (?)
stdin
copy 
5 10 2
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
stdout
copy 
NIE
https://ideone.com/kwpEM3
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!