Rentib

Untitled

Feb 14th, 2020
101
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. bitset<100007> w(0); //odwiedzone wierzchołki
  4. bitset<250007> most(0); //mosty
  5. vector<pair<int, int>> G[100007];
  6. vector<int> cykl_eulera;
  7. int low[100007], preorder[100007], nr;
  8. void DFS(int v = 1, int p = -1) {
  9.     w[v] = 1;
  10.     preorder[v] = low[v] = nr++;
  11.     for(auto i : G[v]){
  12.       if(i.first == p) continue;
  13.       if(w[i.first]) low[v] = min(low[v], preorder[i.first]);
  14.       else{
  15.         DFS(i.first, v);
  16.         low[v] = min(low[v], low[i.first]);
  17.         if(low[i.first] > preorder[v])
  18.           most[i.second] = 1;
  19.       }
  20.     }
  21. }
  22. void update(){
  23.   w.reset();
  24.   most.reset();
  25.   nr = 0;
  26.   DFS();
  27. }
  28. void skasuj(int v, int u){
  29.   for(int i = 0;i < G[v].size();i++)
  30.     if(G[v][i].first == u){
  31.       swap(G[v][i], G[v].back());
  32.       G[v].pop_back();
  33.     }
  34.   for(int i = 0;i < G[u].size();i++)
  35.     if(G[u][i].first == v){
  36.       swap(G[u][i], G[u].back());
  37.       G[u].pop_back();
  38.     }
  39. }
  40. void cykl(){
  41.   int v = 1;
  42.   bool z;
  43.   while(!G[v].empty()){
  44.     update();
  45.     z = 0;
  46.     cykl_eulera.push_back(v);
  47.     for(auto i : G[v]){
  48.       if(most[i.second]) continue;
  49.       skasuj(v, i.first);
  50.       v = i.first;
  51.       z = 1;
  52.       break;
  53.     }
  54.     if(z) continue;
  55.     for(auto i : G[v]){
  56.       skasuj(v, i.first);
  57.       v = i.first;
  58.       break;
  59.     }
  60.   }
  61. }
  62. int main(){
  63.   int n, m; //wierzchokli, krawedzie
  64.   cin >> n >> m;
  65.   for(int i = 0, a, b;i < m;i++){
  66.     cin >> a >> b;
  67.     G[a].emplace_back(b, i);
  68.     G[b].emplace_back(a, i);
  69.   }
  70.   for(int i = 1;i <= n;i++)
  71.     if(G[i].size() % 2 == 1 || G[i].size() == 0){
  72.       cout << "NIE";
  73.       return 0;
  74.     }
  75.   cykl();
  76.   if(cykl_eulera.size() != n){
  77.     cout << "NIE";
  78.     return 0;
  79.   }
  80.   cout << "TAK\n";
  81.   for(auto i : cykl_eulera)
  82.     cout << i << ' ';
  83. }
RAW Paste Data