Mai intai trebuie sa te autentifici.
Cod sursa(job #1609982)
Utilizator | Data | 23 februarie 2016 10:35:34 | |
---|---|---|---|
Problema | Ciclu Eulerian | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.09 kb |
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int nmx = 100002;
int n,m,grad[nmx];
vector <int> g[nmx];
stack <int> st;
void citire() {
scanf("%d %d", &n, &m);
int nod1,nod2;
for(int i = 1; i <= m; ++i) {
scanf("%d %d", &nod1, &nod2);
g[nod1].push_back(nod2);
g[nod2].push_back(nod1);
++ grad[nod2];
++ grad[nod1];
}
}
void euler() {
st.push(1);
while(not st.empty()) {
int nod = st.top();
if(g[nod].size()) {
int aux = g[nod].back();
g[nod].pop_back();
g[aux].erase(find(g[aux].begin(),g[aux].end(),nod));
st.push(aux);
} else {
printf("%d ", nod);
st.pop();
}
}
}
int main() {
freopen("ciclueuler.in", "r", stdin);
freopen("ciclueuler.out", "w", stdout);
citire();
for(int i = 1; i <= n; ++i)
if(grad[i] % 2) {
printf("-1\n");
return 0;
}
euler();
return 0;
}