Pagini recente » Cod sursa (job #1323703) | Cod sursa (job #2241548) | Cod sursa (job #982771) | Cod sursa (job #2220972) | Cod sursa (job #1998956)
#include <fstream>
using namespace std;
ifstream fin("euler.in");
ofstream fout("euler.out");
int n,m,A[300][300],P[300],k,G[300],sol[12000],cnt;
void citire()
{
int x,y;
fin>>n;
while (fin>>x>>y)
{
A[x][y] = A[y][x] = 1;
}
}
int grad(int k)//calculeaza gradul varfului k
{
int s=0;
for(int i=1;i<=n;i++)
if(A[k][i]==1) s++;
return s;
}
void DF(int s)//parcurge graful din varful s si marcheaza varfurile accesibile
{
P[s]=1;
for(int i=1;i<=n;i++)
if(A[s][i]==1 && P[i]==0)
DF(i);
}
int conex()//conexitatea grafului
{
DF(1);
for(int i=1;i<=n;i++)
if(P[i]==0) return 0;
return 1;
}
int euler()//daca este eulerian
{
if(!conex()) return 0;//conex
for(int i=1;i<=n;i++)
if(G[i]%2==1) return 0;//si toate gradele pare
return 1;
}
void ciclu_eulerian(int k)//construieste un ciclu eulerian
{
int maxx=0,nmax=0;
sol[++cnt] = k;//afiseaza varful curent
for(int i=1;i<=n;i++)//cauta varful urmator cu grad maxim
{
if(A[k][i]==1)
if(G[i]>maxx)
{
maxx=grad(i);
nmax=i;
}
}
if(nmax!=0)
{ A[k][nmax]=A[nmax][k]=0;//sterge mughia
G[k]--;//scade gradele
G[nmax]--;
ciclu_eulerian(nmax);//merge in varful urmator
}
}
int main()
{
citire();
for(int i=1;i<=n;i++) G[i]=grad(i);
if(euler())
{
ciclu_eulerian(1);
}
fin.close();
fout << cnt << endl;
for ( int i = 1 ; i <= cnt ; i ++ )
fout << sol[i] << " ";
fout.close();
return 0;
}