My solution of UVA 10054 - The Necklace

 10054 - The Necklace

Background:

Euler : Visited every Edges.
== every nodes are connected and have even connected edges. (Euler Cycle)

Fleury's Algorithm - Find the Euler Cycle.

== Build a new graph by obtaining edge 1 by 1 from the original Euler graph (G).
 * until all edges are visited.
** G MUST always be still an Euler cycle.

Solution to 10054
- Node: color (1-50), Edge:Beam (50,50)
- Build a graph matrix = long G[51][51]
- Build a degree array dgr[51]: dgr[i]=sum of connected edges.


Task 1 - Check connected: 

- use array int p[51];
- int find(int x)

{ 

return (p[x]==x)?x:find(p[x]); 

}

- Verify if all node pair (u,v) are connected?

  if(find(u)==find(v))?

- If 2 nodes have edge, connect them:

  p[find(u)]=find(v);

Task 2 - Check even edges
- If any dgr[i]%2!=0, return false;


Task 3 - Build Euler
for(i=0;!dgr[i];i++);   // find the least node with dgr[i]>0
dfs(i);



int dfs(int u)
{
    int v;
    for(v=1;v<=50;v++)
        if(G[u][v])
        {
            G[u][v]--;

            G[v][u]--;

            dfs(v);
            cout<<v<<" "<<u<<endl;
        }
}