Cod sursa(job #2238948)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 8 septembrie 2018 14:49:15
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

const int NMAX = 100000;
vector< int > v[NMAX+5];

int n;
stack< int > st;

void dfs(int nod, int *f)
{
    for(int i = 0; i < v[nod].size(); i++)
        if(f[v[nod][i]] == 0)
        {
            f[v[nod][i]] = 1;
            dfs(v[nod][i], f);    
        }
}

bool isConex()
{
    int f[n+1];
    for(int i = 0; i <= n; i++)
        f[i] = 0;
    
    f[1] = 1;
    dfs(1, f);
    
    int ok = 1;
    for(int i = 1; i <= n; i++)
    {
        //fout << f[i] << " ";
        if(f[i] == 0)
            ok = 0;
    }
    
    return ok;
}

bool isEuler()
{
    int ok = 1;
    for(int i = 1; i <= n; i++)
        if(v[i].size() & 1)
            ok = 0;
            
    ok = (ok & isConex());
    return ok;
}

void euler(int node)
{
    while(v[node].size() > 0)
    {
        int w;
        w = v[node][0];
        
        v[node].erase(find(v[node].begin(), v[node].end(), w));
        v[w].erase(find(v[w].begin(), v[w].end(), node));
        
        euler(w);
    }
    
    st.push(node);
}

int main()
{
    int m;
    fin >> n >> m;
    
    for(int i = 0; i < m; i++)
    {
        int x, y;
        fin >> x >> y;
        
        v[x].push_back(y);
        v[y].push_back(x);
    }
    
    if(isEuler()) {
        euler(1);
        
        while(st.size() > 1)
        {
            fout << st.top() << " ";
            st.pop();
        }
    }
    else
        fout << "-1";
    
    return 0;
}