Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- bitset<100007> w(0); //odwiedzone wierzchołki
- bitset<250007> most(0); //mosty
- vector<pair<int, int>> G[100007];
- vector<int> cykl_eulera;
- int low[100007], preorder[100007], nr;
- void DFS(int v = 1, int p = -1) {
- w[v] = 1;
- preorder[v] = low[v] = nr++;
- for(auto i : G[v]){
- if(i.first == p) continue;
- if(w[i.first]) low[v] = min(low[v], preorder[i.first]);
- else{
- DFS(i.first, v);
- low[v] = min(low[v], low[i.first]);
- if(low[i.first] > preorder[v])
- most[i.second] = 1;
- }
- }
- }
- void update(){
- w.reset();
- most.reset();
- nr = 0;
- DFS();
- }
- void skasuj(int v, int u){
- for(int i = 0;i < G[v].size();i++)
- if(G[v][i].first == u){
- swap(G[v][i], G[v].back());
- G[v].pop_back();
- }
- for(int i = 0;i < G[u].size();i++)
- if(G[u][i].first == v){
- swap(G[u][i], G[u].back());
- G[u].pop_back();
- }
- }
- void cykl(){
- int v = 1;
- bool z;
- while(!G[v].empty()){
- update();
- z = 0;
- cykl_eulera.push_back(v);
- for(auto i : G[v]){
- if(most[i.second]) continue;
- skasuj(v, i.first);
- v = i.first;
- z = 1;
- break;
- }
- if(z) continue;
- for(auto i : G[v]){
- skasuj(v, i.first);
- v = i.first;
- break;
- }
- }
- }
- int main(){
- int n, m; //wierzchokli, krawedzie
- cin >> n >> m;
- for(int i = 0, a, b;i < m;i++){
- cin >> a >> b;
- G[a].emplace_back(b, i);
- G[b].emplace_back(a, i);
- }
- for(int i = 1;i <= n;i++)
- if(G[i].size() % 2 == 1 || G[i].size() == 0){
- cout << "NIE";
- return 0;
- }
- cykl();
- if(cykl_eulera.size() != n){
- cout << "NIE";
- return 0;
- }
- cout << "TAK\n";
- for(auto i : cykl_eulera)
- cout << i << ' ';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement