
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.
Moderator: Board moderators
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;
}
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 meJulien 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 :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 weeksCode: 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 confess it's horribly slow and ugly, so if anybody has another algo, please tell !
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
}
Yes.adelar wrote:"There may be many solutions, any one of which is acceptable" meaning that the output can be started on any edge...??
Code: Select all
2
6
1 3
1 2
2 3
3 4
3 5
4 5
6
1 2
1 3
2 3
3 4
4 5
3 5
Code: Select all
Case #1
5 3
3 1
1 2
2 3
3 4
4 5
Case #2
5 3
3 1
1 2
2 3
3 4
4 5