Pagini recente » Borderou de evaluare (job #761962) | Cod sursa (job #759817)
Cod sursa(job #759817)
#include<fstream>
#include<list>
#include<queue>
#include<stack>
#define Nmax 100010
#define pb push_back
#define tryNext(C, it) for(typeof(C.begin()) it = C.begin(); it != C.end(); it++)
using namespace std;
list< int > G[Nmax],L;
stack< int > S;
queue< int > Q;
int deg[Nmax],viz[Nmax];
int n,m;
int i;
// citeste
void citeste()
{
int u,v;
scanf("%d %d",&n,&m);
while( m )
{
scanf("%d %d", &u, &v);
G[u].pb(v); deg[u]++;
G[v].pb(u); deg[v]++;
m--;
}
}
//BFS
void BFS( int v )
{
Q.push(v);
viz[v] = 1;
while( !Q.empty() )
{
v = Q.front(); Q.pop();
for(list< int >::iterator w = G[v].begin();w != G[v].end();w++)
if( viz[*w] == 0 )
{
Q.push(*w);
viz[*w] = 1;
}
}
}
// verif conexitate
int conex(int v)
{
BFS(1);
for( int i = 1;i<=n;i++)
if( viz[i] == 0)
return 0;
return 1;
}
// verif eulerian
int eulerian(int v)
{
if( conex(v) == 0 )
return 0;
for(int i = 1; i<=n;i++)
if( deg[i]%2 != 0)
return 0;
return 1;
}
//sterge (v,w)
void sterge( int v, int w )
{
deg[v]--; deg[w]--;
G[v].pop_front();
tryNext(G[w],it)
if( *it == v){
G[w].erase(it);
break;
}
}
// ciclu eulerian
void euler( int v )
{
while(true)
{
if(G[v].empty())
break;
int w = G[v].front();
S.push(v);
sterge(v,w);
v = w;
}
}
// uneste cicluri euleriene
int rez()
{
int v = eulerian(1);
if( v == 0 )
return -1;
do{
euler(v);
v = S.top(); S.pop();
L.push_back(v);
}while( !S.empty() );
return 1;
}
void afis()
{
for(list< int >::iterator it = L.begin(); it!= L.end(); it++)
printf("%d ", *it);
}
int main()
{
freopen("ciclueuler.in", "r", stdin);
freopen("ciclueuler.out", "w", stdout);
citeste();
rez();
afis();
return 0;
}