OJ Board

Posted: **Fri Jun 10, 2005 5:37 pm**

Hello Eduard, this is my first post in board, so you should be very proud, that it trys to help you

i think there is a bug in your prog, the array cv, which stores the eularian circle can become as long as 1000, because you visit one node for every edge. So hence there are 1000 edges you can visit up to 1000 nodes on your way.

Posted: **Fri Jun 10, 2005 6:07 pm**

He is right. Your cv should have size 1001
By the way, when I submit your code, it gets TLE
And I see no point to use Floyd. You can solve the problem in O(E) time

Posted: **Fri Jun 10, 2005 6:45 pm**

and that is right too, especially by better your runtime complexity you can even shorten your program. when you just test if all nodes have odd degree and after that do your solve procedure this is enough. you just have to check weather all edges have been used to create the circle. if not all edges used then the graph wasnt connected...

yeah i tested it now, i got your code acc just leting procedure floyd away and do what i sayed

Posted: **Sat Jun 11, 2005 9:54 am**

Thanks everybody.Now I got AC.Yes The Bug was on My Cv array length.
I cut my code too.
Thanks once again.
Eduard

Posted: **Mon Jul 11, 2005 5:03 am**

Hi,

I tried to solve this problem but I got WA only.

My program:
* Calc one euler cicle C
* For all vertex not in C, calc euler cicle c and union with C

This is my code:

Code: Select all

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
using namespace std;

#define V(c) vector <c>
#define ALL(c) (c).begin(),(c).end()
#define FOR(i,v,n) for(int i=v,_n=n;i<_n;++i)
#define FORD(i,v,n) for(int i=(n-1),_v=v;i>=_v;--i)
#define REP(i,n) FOR(i,0,n)
#define REPD(i,n) FORD(i,0,n)
#define FOREACH(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define sz(c) (c).size()

int G[51][51],grau[51],usado[51],vis[51];
void calc(vector<pair<int,int> >& res, int i) {
  REP(j,50) if (G[i][j]>0) {
    G[i][j]--;
    G[j][i]--;

    vis[i]=vis[j]=1;

    res.push_back(make_pair(i+1,j+1));
    calc(res,j);
    break;
  }
}

int main( int argc, char* argv[] ) {

  int ncasos, caso=1;
  cin>>ncasos;

  while(ncasos--) {
    int N;
    cin>>N;

    // limpando
    memset(G,0,sizeof(G));
    memset(grau,0,sizeof(grau));
    memset(usado,0,sizeof(usado));
    memset(vis,0,sizeof(vis));

    // lendo
    REP(i,N) {
      int u,v; 
      
      cin>>u>>v;
      u--; v--;

      G[u][v]++;
      G[v][u]++;
      grau[u]++;
      grau[v]++;

      usado[u]=1;
      usado[v]=1;
    }

    vector<pair<int,int> > res;
    cout<<"Case #"<<caso++<<endl;

    REP(i,51) if (grau[i]>0) {
      calc(res, i);
      break;
    }

    bool flag=true;
    REP(i,51) REP(j,51) if (flag && G[i][j]>0) {
      vector<pair<int,int> > novo;
      calc(novo, i);

      bool flag2=false;
      REP(r,sz(res)) {
	if (res[r].second == novo.front().first &&
	    res[(r+1)%sz(res)].first == novo.back().second) {

	  vector<pair<int,int> > novoRes;
	  REP(i,r+1)
	    novoRes.push_back(res[i]);
	  REP(i,sz(novo))
	    novoRes.push_back(novo[i]);
	  FOR(i,r+1,sz(res))
	    novoRes.push_back(res[i]);

	  res=novoRes;

	  flag2=true;
	  break;
	}
      }
      if (!flag2) {
	flag=false;
	break;
      }
    }

    if (!flag || sz(res)<N || res.back().second != res.front().first) {
      cout<<"some beads may be lost"<<endl<<endl;
      continue;
    }
    REP(i,sz(res)) {
      cout<<res[i].first<<" "<<res[i].second<<endl;
    }
    cout<<endl;
  }
  return 0;
}

Thanks.

Posted: **Sat Jul 30, 2005 10:07 am**

Julien Cornebise wrote: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 !

Yes I know a better way that uses a linked list and adjacency matrix to get O(n) running time. I do not take credit for the following code, it was not written by me

Code: Select all


list< int > cyc;
void euler( list< int >::iterator i, int u ) {
  for( int v = 0; v < n; v++ ) if( graph[u][v] ) {
    graph[u][v] = graph[v][u] = false;
    euler( cyc.insert( i, u ), v );
  }
}

int main() {
  // read graph into graph[][] and set n to the number of vertices
  euler( cyc.begin(), 0 );
  // cyc contains an euler cycle starting at 0
}

Enjoy

Posted: **Mon Oct 17, 2005 7:50 pm**

One test case that might be useful:

1
4
1 1
1 2
1 2
2 2

I hope it helps.

Posted: **Sat Dec 02, 2006 6:15 am**

Another test case that could help debug WA is:
1
9
2 4
1 1
1 2
1 2
2 2
3 3
4 4
3 2
4 3

Hope it helps all!

Posted: **Fri Jun 08, 2007 5:21 pm**

hi,,,
"There may be many solutions, any one of which is acceptable" meaning that the output can be started on any edge...??
that's in advance...

Posted: **Sat Jun 09, 2007 12:36 am**

adelar wrote:"There may be many solutions, any one of which is acceptable" meaning that the output can be started on any edge...??

Yes.

Posted: **Mon Jun 11, 2007 4:11 pm**

hi,
to input above
1 4 1 1 1 2 1 2 2 2
my algorithm have output:
1 1
1 2
2 2
which is the correct output?
thanks.

Posted: **Mon Jun 11, 2007 7:49 pm**

My accepted code returns...

Output:

Code: Select all

Case #1
1 1
1 2
2 2
2 1

Hope it helps.

Posted: **Thu Jun 14, 2007 11:17 pm**

Hi,
someone have other input case... to all input test that I have my code output correct answer... but have WA in 5.115 s ...
thanks in advance..

Posted: **Mon Jun 25, 2007 9:05 pm**

Hi,
which is the output to this input:

Code: Select all

my code output to this case:

Code: Select all

thanks in advance...

Posted: **Mon Jun 25, 2007 9:11 pm**

Your output is correct. This problem has a special corrector. So, different but correct answers should be accepted.

OJ Board

10054 - The Necklace

Test case.

I donts understand how the output can be printed...

Re: I donts understand how the output can be printed...

test case above

INPUTS

out