Cod sursa(job #589233)

Utilizator costyv87Vlad Costin costyv87 Data 11 mai 2011 16:39:17
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <list>
#include <deque>
#include <stack>
#include <vector>
using namespace std;


FILE *f,*g;

int gr[100100];
bool bif[100100];
stack <int > S;
deque <int> q;
vector <int> sol;
list <int> a[100100];
int i,n,m,x,y;
bool ok;

void bf() {
int w;
q.push_back(1);
bif[1]=true;

while (q.size()>0) {
	w=q.front();
	q.pop_front();
	
	for (list <int>::iterator j=a[w].begin();j!=a[w].end();j++) 
		if (bif[*j]==false) {
			bif[*j]=true;
			q.push_back(*j);
			}
	
	}

}


void del(int j, int i) {

for (list<int>::iterator q=a[j].begin();q!=a[j].end();q++) 
	if (*q==i) {
		a[j].erase(q);
		break;
		}

}

void euler(int i) {
int j;

i=1;

while (1==1) {
	if (a[i].empty()) {
		break;
		}
	j=a[i].back();
	a[i].pop_back();
	del(j,i);
	S.push(j);
	i=j;
	}


}



int main() {
f=fopen("ciclueuler.in","r");
g=fopen("ciclueuler.out","w");

fscanf(f,"%d%d",&n,&m);
for (i=1;i<=m;i++) {
	fscanf(f,"%d%d",&x,&y);
	a[x].push_back(y);
	a[y].push_back(x);
	gr[x]++;
	gr[y]++;
	}

ok=true;
for (i=1;i<=n;i++) 
	if (gr[i]%2==1) 
		ok=false;
bf();
for (i=1;i<=n;i++)
	if (bif[i]==false)
		ok=false;
	
	
if (ok==false) {
	fprintf(g,"-1");
	fclose(g);
	return 0;
	}

int x;
//fprintf(g,"1 ");
x=1;
do {  
	euler( x );         
	x = S.top(); S.pop(); 
	sol.push_back( x ); 
    } 
while( !S.empty() ); 


for (i=0;i<sol.size();i++)
	fprintf(g,"%d ",sol[i]);

fclose(g);
return 0;
}