## 10054 - The Necklace

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

### 10054 - The Necklace

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
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am

### Re Help

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
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am
I got wa on this problem, could someone give me some test case?

Thanks before.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
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
New poster
Posts: 15
Joined: Sun Dec 15, 2002 2:51 pm
how?

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
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
New poster
Posts: 6
Joined: Mon Nov 17, 2003 3:39 pm

### construction of the final cycle

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
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
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
New poster
Posts: 10
Joined: Mon Oct 18, 2004 3:52 pm

### Anything Wrong?

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>

char e;
char t;
char c;
/* degree counter of each vertex */
int d;
/* 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 );
d++;
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 */
/* 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]--;
}
for ( u=1;u<=50;u++ )
{
if ( adj[u][v] )
break;
}
}
/* p is the length of the newly found cycle */
return p;
}
[/c]

kasparov
New poster
Posts: 5
Joined: Wed Oct 20, 2004 7:36 pm

### Plz help, still WA

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

#define cin in

int conn;
int Conn;
int nEdges;

// 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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

### 10054-The Neacklace

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.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

liux0229
New poster
Posts: 8
Joined: Thu May 20, 2004 1:30 pm
Location: China
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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
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.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

liux0229
New poster
Posts: 8
Joined: Thu May 20, 2004 1:30 pm
Location: China
Maybe you can post your code here or send it to me liux@qilongzhu.com

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
Here is my code.

Code: Select all

``````ACCEPTED
``````
Last edited by Eduard on Sat Jun 11, 2005 9:59 am, edited 1 time in total.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650