Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int X[100002], Y[100002], n, m;
- /// (X[i], Y[i]) - muchie din graf
- vector<int> L[100002];
- /// L[i] = indicii muchiilor incidente cu i
- int viz[100002]; /// viz este pentru MUCHIILE deja vizitate
- int t[100002]; /// verificarea conexitatii
- int q[100002], ind; /// memorez ciclul eulerian
- ifstream fin("euler.in");
- ofstream fout("euler.out");
- void Citire()
- {
- int i, j;
- fin >> n;
- m = 0;
- while(fin >> i >> j)
- {
- m++;
- X[m] = i;
- Y[m] = j;
- L[i].push_back(m);
- L[j].push_back(m);
- }
- }
- void DFS(int k)
- {
- int i;
- for(auto i : L[k])
- if(viz[i] == 0) /// muchia i este nevizitata
- {
- viz[i] = 1;
- DFS(X[i] + Y[i] - k);
- }
- q[++ind] = k;
- }
- void DFS1(int k)
- {
- int i, j;
- t[k] = 1;
- for(i=0; i<L[k].size(); i++)
- {
- j = L[k][i];
- if(t[j] == 0) DFS1(j);
- }
- }
- int ToateGradelePare()
- {
- int i;
- for(i=1; i<=n; i++)
- if(L[i].size() % 2 == 1) return 0;
- return 1;
- }
- int EsteEulerian()
- {
- int i;
- if(!ToateGradelePare()) return 0;
- DFS1(1);
- /// Caut noduri nevizitate de grad nenul
- for(i=1; i<=n; i++)
- if(t[i] == 0 && L[i].size() > 0) return 0;
- return 1;
- }
- int main()
- {
- int i;
- Citire();
- if(!EsteEulerian()) fout << "-1";
- else
- {
- DFS(1);
- fout << ind << endl;
- for(i=1; i<=ind; i++)
- fout << q[i] << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement