10054 - The Necklace

[10153EN]

I am poor at graph problems. In this problem I can check for whether a suitable necklace exists, i.e. Yes or No. But I find it difficult to print out the sequence of segments.

Could anyone share his or her experience~

THx

[Amir Aavani]

hi

it is not that hard !

[pascal]
MainLoop := FindLoopInGraph;

while (there is a loop in graph) do
begin
if there is a node that exist in MainLoop then
begin
TempLoop := FindaLoopInGraph;
Add TempLoop to MainLoop
end;
end;
[/pascal]

note that FindLoopInGraph delete the edges which are used in returning cycle.[quote][/quote]

[b3yours3lf]

I got wa on this problem, could someone give me some test case?

Thanks before.

[Julien Cornebise]

I'm having WA too !
My algo is a simple Eulerian cycle on the graph of the colors as vertices and the beads as the edges. Where can I fail please ?
Any idea is welcome !

[abc]

how?

[Julien Cornebise]

Well, I got AC this afternoon. Given that it was my first Eulerian cycle, I was mistaking in the construction of the final cycle from the direct cycles found via dfs.
It's really slow, though (5.7 sec !). Anyone would have a link to a nice implementation of eulerian cucle search please ?

[deneb]

Hi:
I can find the direct cycles as well as you but i',m getting mad about creating the final cycle. Please, give me any hint.
Thnx

[Julien Cornebise]

Hi Deneb

I had much troubles with this part, and that's what makes my code so ugly and so slow
The algorithm is as follows :

Code: Select all

/* I don't mention global variables used to mark the cycles and to store the eulerian cycle */
/* direct_cycle is the direct cycle you're processing */
construct_eulerian_cycle(direct_cycle) {
Mark this cycle;
For each vertex in the cycle {
     Add the vertex to the eulerian cycle:
     For all non-marked cycles C containing this vertex {
           construct_eulerian_cycle(C);
     }
}

I hope this pseudo code is clear enough and not too much wrong (I've got the brain bottom-up because of christmas parties AND working my final exams wich are in two weeks ).

I confess it's horribly slow and ugly, so if anybody has another algo, please tell !

[zhenh]

I am getting WAs, but I can't see why.
Or could someone give me some test cases?
thanks.

[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int adj[51][51];
char e[2000];
char t[2000];
char c[2000];
/* degree counter of each vertex */
int d[51];
/* edge counter */
int D;

/* Eulerian cycle for undirected graph */
int find_cycle( int s );

int main( int argc, char *argv[] )
{
int i,v,u;
int p,le,j,k;
int tc,nb,case_count;

fscanf( stdin, "%d", &tc );
case_count=0;
BEGIN:
while ( case_count < tc )
{
memset( adj, 0, 51*51*sizeof(int) );
memset( e, 0, sizeof(e) );
memset( t, 0, sizeof(t) );
memset( c, 0, sizeof(c) );
memset( d, 0, sizeof(d)*sizeof(int) );
D = 0;
fscanf( stdin, "%d", &nb );
i = nb;
/* bead reader, also create a graph */
while ( i > 0 )
{
fscanf( stdin, "%d%d", &u, &v );
adj[v]++;
d++;
adj[v]++;
d[v]++;
D++;
i--;
}
for ( u=1;u<=50;u++ )
{
if ( d % 2 != 0 )
{
if ( case_count > 0 )
fprintf( stdout, "\n" );
case_count++;
fprintf( stdout, "Case #%d\nsome beads may be lost\n", case_count );
goto BEGIN;
}
else if ( d != 0 )
v = u;
}
/* obtain an initial cycle */
find_cycle( v );
strcpy( e, c );
p=1;
while ( p )
for ( i=0,le=strlen(e);i<le;i++ )
{
p=0;
if ( d[e] > 0 )
{
/* there exist a cycle contain at least one vertex of current cycle e,
find it and merge it into e */
p=find_cycle(e);
for ( j=0;j<=i;j++ )
t[j]=e[j];
for ( k=i+1;k<=i+p;k++ )
t[k]=c[k-i];
for ( j=i+p+1;j<=le+p;j++ )
t[j]=e[j-p];
}
}

if ( case_count > 0 )
fprintf( stdout, "\n" );
case_count++;
fprintf( stdout, "Case #%d\n", case_count );
for ( i=0;i<strlen(e);i++ )
{
fprintf( stdout, "%d %d\n", e, e[i+1] );
i++;
}
}
return 0;
}

int find_cycle( int s )
{
int v,u,p;
int k;
v=s;
p=0;
for ( u=1;u<=50;u++ )
{
if ( adj[s] )
break;
}
if ( u>50 )
return 0;
while ( u<=50 )
{
c[p++]=v;
c[p++]=u;
/* delete the edge from the graph */
adj[v]--;
adj[v]--;
/* decrease degree counters */
D--;
d--;
d[v]--;
v=u;
/* take care of multiple edges */
for ( k=0;k<adj[u];k++ )
{
c[p++]=u;
D--;
d[u]--;
}
adj[u][u]=0;
for ( u=1;u<=50;u++ )
{
if ( adj[u][v] )
break;
}
}
/* p is the length of the newly found cycle */
return p;
}
[/c]

[kasparov]

#include <iostream>
#include <fstream>
using namespace std;

#define cin in

int conn[52][52];
int Conn[52][52];
int nEdges[52];

// To check weather this node is connected or not.
void IsConnected(int node)
{
for(int i=1; i<51; i++)
{
if (Conn[node] > 0)
{
Conn[node]--;
Conn[node]--;
IsConnected(i);
}
}
}

// To check wheather a node is isolated or not
bool IsIsolated(int x)
{
int sol= 0;
for(int i=1; i<51; i++)
{
if(conn[x] != 0)
sol++;
}
return sol<=1;
}

//To check weather the connection from me to x is a bridge or not.
bool IsBridge(int x, int me)
{
if(IsIsolated(x)) return true;
for(int i=1; i<51; i++)
{
if(me!=i && conn[x] != 0 && !IsIsolated(i))
return false;
}
return true;
}

// To get a next "good" node for x
int getNext(int x)
{
int tryIt=0;
for(int i=1 ; i<51 ; i++)
{
if(conn[x]!=0)
{
tryIt = i;
if(!IsBridge(i, x))
{
cout << x << " " << i << endl;
conn[x]--;
conn[x]--;
return i;
}
}
}
if (tryIt==0)
return 0;
cout << x << " " << tryIt << endl;
conn[x][tryIt]--;
conn[tryIt][x]--;
return tryIt;
}

// To get a valid fisrt node
int getFirst()
{
int i;
for(i=1; i<51; i++)
{
int j;
for(j=1; j<51; j++)
if(!conn[j])
return i;
}
}

//Here we solve
bool SolveFromMain()
{
int i;
for(i=0; i<51; i++)
{
if(nEdges%2 != 0)
return false;
}

int x = getFirst();

////////// To check the connected condition
IsConnected(x);
for(i=1; i<51; i++)
for(int j=1; j<51; j++)
if(Conn[i][j] >0)
return false;
/////////////////////////////////////////////

while(x!=0)
{
x = getNext(x);
}
return true;
}

void intialize()
{
int i;
for(i = 0 ; i<51; i++)
{
int j;
for(j=0; j<51; j++)
{
conn[i][j]=0;
conn[j][i]=0;
Conn[i][j]=0;
Conn[j][i]=0;
}
}
for(i=0; i<51; i++)
nEdges[i] = 0;
}

void main()
{
ifstream in("test.in");

int n, n2, x, y;
cin >> n;

int i;
for (i=0 ; i<n ; i++)
{
intialize();
cin >> n2;
int j;
for(j=0 ; j<n2 ;j++)
{
cin >> x >> y;
nEdges[x]++;
nEdges[y]++;
conn[x][y]++;
Conn[x][y]++;
conn[y][x]++;
Conn[y][x]++;
}
cout << "Case #" << i+1 << endl;
if(!SolveFromMain())
cout << "some beads may be lost" << endl;
if(i<n-1)
cout << endl;
}
}

[Eduard]

I'm getting WA 10054.
My algo is as follows.
1.Check if there isn't any vertex with odd degree.
2.Check if graph is connected or not.
3.Find euler cycle.
Please give me some tests or some hints.And if someone can give some other Euler cycle problems.
Thanks
Eduard.

[liux0229]

Hi !
Your algo is right.
Try this out:
1
5
1 10
10 20
20 30
30 40
40 1
Make sure your program doesn't report "some beads may be lost"

[Eduard]

Hello liux0229
Thanks for answering after for 4 months.
My program gives for yout input this and I think correct output.

Code: Select all

Case #1
1 40
40 30
30 20
20 10
10 1

May be you can give some other tests?
Thanks.

[liux0229]

Maybe you can post your code here or send it to me liux@qilongzhu.com

[Eduard]

Here is my code.

Code: Select all

ACCEPTED