Cod sursa(job #922537)

Utilizator krissu93FMI Tiugan Cristiana Elena krissu93 Data 22 martie 2013 13:08:25
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;


vector<int> vecini[100000];
int ciclu[100000];
int viz[100000];
int nr=0;

void parc_ad(int nod){
viz[nod]=1;
for (int contor=0;contor<vecini[nod].size();contor++)
    if (viz[vecini[nod][contor]]==0)
    parc_ad(vecini[nod][contor]);
}
bool check(int noduri){
parc_ad(1);
for (int i=1;i<=noduri;i++)
    {if (viz[i]==0)
        return false;
     if (vecini[i].size()%2!=0)
        return false;
    }
    return true;
}
void get_data(int&noduri,int&muchii){
ifstream in("ciclueuler.in");
in>>noduri>>muchii;

for (int contor=0;contor<muchii;contor++){
    int nod1,nod2;
    in>>nod1>>nod2;
    vecini[nod1].push_back(nod2);
    vecini[nod2].push_back(nod1);
}
in.close();
}

void euler(int nod){

while (vecini[nod].size()!=0){
    int nod2=vecini[nod].back();
    vecini[nod].pop_back();
    for (int i=0;i<vecini[nod2].size();i++)
    if (vecini[nod2][i]==nod){
        vecini[nod2][i]=vecini[nod2].back();
        vecini[nod2].pop_back();
        break;
    }
    euler(nod2);
}
ciclu[nr++]=nod;
}

int main(){

int noduri,muchii;
get_data(noduri,muchii);
ofstream out("ciclueuler.out");
if (check(noduri)==false) out<<-1;
else{
euler(1);
for (int contor=0;contor<muchii;contor++) out<<ciclu[contor]<<' ';
}
return 0;
}