OJ Board

Code: Select all

AC

Code: Select all

Remove after Acc

Code: Select all

  if(even(graph) || !conected(graph))
     "some beads may be lost"
  else
      print euler path;

Code: Select all

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int grafo[51][51];
int grado[51];
int grado_aux[51];
bool activo[51];
int visitado[51];
queue<int> colita;
queue<int> cola;
int vtrue;
int primero;
int abalorios;

void borrar() {
  for(int i = 0; i <= 50; i++) {
    for(int j = 0; j <= 50; j++) { 
      grafo[i][j] = 0;
     }
    grado[i] = 0;
    grado_aux[i] = 0;
    activo[i] = false;
    visitado[i] = 0;
  }
  while(!cola.empty()) cola.pop();
}

void leer() {
  int n, m;
  
  scanf("%d", &abalorios);
  
  scanf("%d%d", &n, &m);
  grafo[n][m]++;
  grafo[m][n]++;
  grado[n]++;
  grado[m]++;
  grado_aux[n]++;
  grado_aux[m]++;
  primero = n;
  activo[n] = true;
  activo[m] = true;

  for(int i = 1; i < abalorios; i++) {
    scanf("%d%d", &n, &m);
    activo[n] = true;
    activo[m] = true;
    grafo[n][m]++;
    grafo[m][n]++;
    grado[n]++;
    grado[m]++;
    grado_aux[n]++;
    grado_aux[m]++;
  }
}

void bfs(int vertice) {
  int aux;

  while(!colita.empty()) colita.pop();

  vtrue++;
  colita.push(vertice);
  visitado[vertice] = vtrue;
  while(!colita.empty()) {
    aux = colita.front();
    colita.pop();
    for(int i = 1; i <= 50; i++) {
      if(grafo[aux][i] > 0 && visitado[i] != vtrue) {
	colita.push(i);
	visitado[i] = vtrue;
      }
    }
  }
}

bool euleriano() {

  sort(grado_aux, grado_aux+51);

  for(int i = 50; i > 0 && grado_aux[i] > 0; i--)
    if(grado_aux[i] % 2) return false;

  return true;
}

bool conectado(int vertice) {

  bfs(vertice);

  for(int i = 1; i <= 50; i++)
    if(activo[i] && visitado[i] != vtrue)
      return false;
  
  return true;
}

void imprime_sol() {

  int aux;
  int aux2;
  while(!cola.empty()) {
    aux = cola.front();
    cola.pop();
    aux2 = cola.front();
    cola.pop();
    printf("%d %d\n",aux, aux2);
  }
}

int busca_siguiente(int vertice) {

  int i;
  int candidato;

  if(grafo[vertice][vertice] > 0) {
    grafo[vertice][vertice] -= 2;
    return vertice;
  }

  for(i = 1; i <= 50; i++){
    if(grafo[vertice][i] > 0) {
      candidato = i;
      grafo[vertice][i]--;
      grafo[i][vertice]--;
      grado[i]--;
      grado[vertice]--;
      if(grado[i] <= 0) activo[i] = false;
      if(grado[vertice] <= 0) activo[i] = false;
      if(conectado(i)) 
	return i;
      else {
	grafo[vertice][i]++;
	grafo[i][vertice]++;
	grado[i]++;
	grado[vertice]++;
	activo[i] = true;
	activo[vertice] = true;
      }
    }
  }
  return -1;
}

bool calcula_sol() {
  int v1 = primero;
  int v2;

  while(abalorios) {
    v2 = busca_siguiente(v1);
    if(v1 < 0) return false;
    abalorios--;
    grado[v1]--;
    grado[v2]--;
    if(grado[v1] <= 0) activo[v1] = false;
    if(grado[v2] <= 0) activo[v2] = false;
    cola.push(v1);
    cola.push(v2);
    v1 = v2;
  }
  return true;
}

int main() {
  int casos;

  scanf("%d", &casos);  
  for(int caso = 1; caso <= casos; caso++){
    vtrue = 0;
    borrar();
    leer();
    printf("Case #%d\n", caso);
    if(euleriano() && conectado(primero)) {
      if(!calcula_sol()) 
	printf("some beads may be lost\n");
      else
	imprime_sol();
    }else{
      printf("some beads may be lost\n");
    }    

    if(caso < casos)     
      printf("\n");
  }

  return 0;
}

Code: Select all

2
5
50 50
50 50
50 50
50 50
50 50
6
1 50
1 50
1 50
1 50
1 50
1 50

Code: Select all

Case #1
50 50
50 50
50 50
50 50
50 50

Case #2
1 50
50 1
1 50
50 1
1 50
50 1

Code: Select all

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

struct node
{
	short num;
	node *next;
};

struct color
{
	short co;
	node *now,*head,*last;
}c[51];

short in[50],w;

bool DFS(short a,short &dest,bool v[])
{
	v[a]=false;
	c[a].now=c[a].head;
	do
	{
		if(c[a].now->num==dest)	return true;
		if(v[c[a].now->num]&&DFS(c[a].now->num,dest,v))	return true;
		c[a].now=c[a].now->next;
	}while(c[a].now);
	return false;
}

void DFS(short a,bool v[])
{
	v[a]=false;
	c[a].now=c[a].head;
	do
	{
		if(v[c[a].now->num])
		{
			DFS(c[a].now->num,v);
		}
		c[a].now=c[a].now->next;
	}while(c[a].now);
}

void run(short &s,bool v[])
{
	short i,a=s,b,t=0;
	while(t<c[s].co)
	{
		while(1)
		{
			node *n,*m;
			n=c[a].head;
			b=n->num;
			c[a].head=n->next;
			m=c[b].head;
			if(m->num==a)	c[b].head=m->next;
			else
			{
				while(m->next->num!=a)	m=m->next;
				c[b].now=m;
				m=c[b].now->next;
				if(m==c[b].last)	c[b].last=c[b].now;
				c[b].now->next=m->next;
			}
			for(i=0;i<w;i++)	v[in[i]]=true;
			if(a==b||n->next==NULL||DFS(a,b,v))
			{
				delete n,m;
				break;
			}
			c[a].last->next=n;
			c[a].last=n;
			c[a].last->next=NULL;
			c[b].last->next=m;
			c[b].last=m;
			c[b].last->next=NULL;
		}
		if(a==s)	t++;
		if(b==s)	t++;
		cout<<a<<' '<<b<<endl;
		a=b;
	}
}

void create(short &a,short &b)
{
	short i;
	for(i=0;i<w;i++)
		if(a==in[i])	break;
	if(i==w)	in[w++]=a;
	node *newnode=new node;
	c[a].co++;
	newnode->num=b;
	newnode->next=NULL;
	if(c[a].head==NULL)
	{
		c[a].now=c[a].head=newnode;
	}
	c[a].now->next=newnode;
	c[a].now=newnode;
}

bool even()
{
	for(short j=0;j<w;j++)
	{
		if(c[in[j]].co&1)	return false;
		c[in[j]].last=c[in[j]].now;
	}
	return true;
}

bool connect(short &a,bool v[])
{
	short j;
	for(j=0;j<w;j++)	v[in[j]]=true;
	DFS(a,v);
	for(j=0;j<w;j++)
		if(v[in[j]])	return false;
	return true;
}

int main()
{
	short n,m,a,b,i,j;
	bool isStart=false,v[51];
	cin>>n;
	in[0]=0;
	for(i=1;i<=n;i++)
	{
		w=0;
		if(isStart)	cout<<endl;
		else	isStart=true;
		cin>>m;
		for(j=1;j<51;j++)
		{
			c[j].co=0;
			c[j].head=NULL;
		}
		cin>>a>>b;
		in[w++]=a;
		create(a,b);
		create(b,a);
		for(j=1;j<m;j++)
		{
			cin>>a>>b;
			create(a,b);
			create(b,a);
		}
		cout<<"Case #"<<i<<endl;
		if(even()&&connect(a,v))
		{
			run(a,v);
		}
		else	cout<<"some beads may be lost\n";
	}
	return 0;
}

Code: Select all

1

4
1 2
2 2
2 1
1 1