fork download
copy 
  1. /*
  2. http://b...content-available-to-author-only...j.com/problems/MESA/
  3.  
  4. 3 3
  5. 1 2
  6. 2 3
  7. 1 3
  8. 4 3
  9. 1 2
  10. 1 3
  11. 1 4
  12. 27 4 
  13. 24 1 
  14. 17 14 
  15. 24 23 
  16. 23 14
  17. 5 3 
  18. 1 2 
  19. 3 4 
  20. 4 5 
  21.  
  22. */
  23.  
  24. #include <stdio.h>
  25. #include <string.h>
  26. using namespace std;
  27.  
  28. #define MAX_VERTICES 100
  29.  
  30. bool mesa[MAX_VERTICES][MAX_VERTICES];
  31. int lado[MAX_VERTICES];
  32.  
  33. bool biparticao(int n, int vert,int lados=1){
  34. 	lado[vert]=lados;
  35. 	int ladoAtual=lados;
  36. 	bool ret = true;
  37. 	if(lados==1){
  38. 		lados=2;
  39. 	}else{
  40. 		lados=1;
  41. 	}
  42. 	for(int i=0;i<n;i++){
  43. 		if(mesa[vert][i]){
  44. 			if(!lado[i]){
  45. 				ret=biparticao(n,i,lados);
  46. 			}else{
  47. 				if(lado[i]==ladoAtual){
  48. 					return false;
  49. 				}
  50. 			}
  51. 			if(!ret){
  52. 				return false;
  53. 			}
  54. 		}
  55. 	}
  56. 	return ret;
  57. }
  58.  
  59. int main(){
  60. 	int n; //Numero de convidados
  61. 	int m; //Ligações entre os convidados
  62.  
  63. 	int u,v; //Quem é amigo de quem
  64.  
  65. 	bool bipartido;
  66.  
  67. 	int cont = 0;
  68.  
  69. 	while (scanf("%d %d",&n,&m)==2 && n!=EOF){
  70. 		for(int i=0;i<n;i++){
  71. 			memset(mesa[i],0,sizeof(int)*n);
  72. 			lado[i]=0;
  73. 		}
  74. 		for(int i=0;i<m;i++){
  75. 			scanf("%d %d",&u,&v);
  76. 			mesa[u-1][v-1]=true;
  77. 			mesa[v-1][u-1]=true;
  78. 		}
  79.  
  80. 		bipartido = true;
  81. 		for(int i=0; i<n; i++){
  82. 			if(lado[i]==0 && !biparticao(n,i)){
  83. 				bipartido = false;
  84. 				break;
  85. 			}
  86. 		}
  87. 		cont++;
  88. 		printf("Instancia %d\n",cont);		
  89. 		if(bipartido){
  90. 			printf("sim\n\n");
  91. 		}else{
  92. 			printf("nao\n\n");
  93. 		}
  94.  
  95. 	}
  96. 	return 0;
  97. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
3 3
1 2
2 3
1 3
4 3
1 2
1 3
1 4
27 4 
24 1 
17 14 
24 23 
23 14
5 3 
1 2 
3 4 
4 5
stdout
copy 
Instancia 1
nao

Instancia 2
sim

Instancia 3
sim

Instancia 4
sim
https://ideone.com/eFZX5Q
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!