Page 1 of 5

10054 - The Necklace

Posted: Sat Jun 29, 2002 8:51 pm
by 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

Re Help

Posted: Wed Apr 16, 2003 6:39 am
by Amir Aavani
hi

it is not that hard ! :wink:

[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]

Posted: Tue Aug 19, 2003 10:50 am
by b3yours3lf
I got wa on this problem, could someone give me some test case?

Thanks before.

Posted: Wed Oct 01, 2003 7:28 pm
by 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 :) !

Posted: Wed Oct 01, 2003 10:40 pm
by abc
how?

Posted: Thu Oct 02, 2003 1:00 am
by 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 ?

construction of the final cycle

Posted: Mon Dec 29, 2003 3:30 am
by 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

Posted: Mon Dec 29, 2003 10:27 am
by Julien Cornebise
Hi Deneb

I had much troubles with this part, and that's what makes my code so ugly and so slow :oops:
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 !

Anything Wrong?

Posted: Wed Dec 15, 2004 4:24 pm
by 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]

Plz help, still WA

Posted: Thu Jan 27, 2005 9:45 pm
by 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;
}
}

10054-The Neacklace

Posted: Wed Feb 02, 2005 6:11 pm
by 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.

Posted: Wed Jun 08, 2005 5:14 pm
by 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"

Posted: Thu Jun 09, 2005 1:24 pm
by 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.

Posted: Thu Jun 09, 2005 2:30 pm
by liux0229
Maybe you can post your code here or send it to me liux@qilongzhu.com

Posted: Thu Jun 09, 2005 8:10 pm
by Eduard
Here is my code.

Code: Select all

ACCEPTED