Mai intai trebuie sa te autentifici.
Cod sursa(job #2208265)
Utilizator | Data | 28 mai 2018 23:39:38 | |
---|---|---|---|
Problema | Ciclu Eulerian | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.41 kb |
#include <stdio.h>
#include <vector>
#include <deque>
#include <bitset>
using namespace std;
FILE *f,*g;
vector <pair <int,int> > nod[100002];
deque <int> q;
bitset <500008> viz;
int n,m;
void eulerian(int no)
{
int muchie,vecin;
while(nod[no].size())///mai are vecini
{
muchie=nod[no].back().second;///ordinul muchiei
vecin=nod[no].back().first;
nod[no].pop_back();///eliminam vecinul
if(!viz[muchie])///nu am mai trecut prin muchia asta
viz[muchie]=1,eulerian(vecin);///mergem la urmatorul nod
}
q.push_back(no);///daca din nodul no nu mai putem merge in niciun alt nod, il introducem in coada finala
}
int main()
{
int x,y;
f=fopen("ciclueuler.in","r");
g=fopen("ciclueuler.out","w");
fscanf(f,"%d %d",&n,&m);
for(int i=1;i<=m;++i)
{
fscanf(f,"%d %d",&x,&y);
nod[x].push_back({y,i});///nodul x are ca si vecin nodul y si muchia dintre ele este de ordinul i;
nod[y].push_back({x,i});///idem
}
for(int i=1;i<=n;++i)
if(nod[i].size() % 2)///nodul i nu are grad par, deci nu admite ciclu Eulerian
{
fprintf(g,"-1\n");
return 0;
}
eulerian(1);
q.pop_back();
while(!q.empty())
{
int x=q.front();
fprintf(g,"%d ",x);
q.pop_front();
}
fclose(f);
fclose(g);
return 0;
}