SHARE
TWEET

Untitled

solsampaio18 Oct 14th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. /*-------------------------------------------------------------------*\
  3. |  grafos0.h  --- TAD para implementacao de grafo dirigido SEM pesos  |
  4. |                                                                     |
  5. |    Vers�o simplificada;  |V| <=  MAXVERTS;                          |
  6. |     Assume-se que os v�rtices s�o numerados de 1 a |V|.             |
  7. |                                                                     |
  8. |   A.P.Tom�s, CC2001 (material para prova pratica), DCC-FCUP, 2017   |
  9. |   Last modified: 2017.12.18                                         |
  10. \--------------------------------------------------------------------*/
  11.  
  12. #include <stdlib.h>
  13.  
  14. #define MAXVERTS 20000
  15. // numero maximo de vertices (alterar se necessario)
  16.  
  17.  
  18. typedef struct arco {
  19.   int no_final;
  20.   struct arco *prox;
  21. } ARCO;
  22.  
  23. typedef struct no {
  24.   //int label;
  25.   ARCO *adjs;
  26. } NO;
  27.  
  28. typedef struct graph {
  29.   NO verts[MAXVERTS+1];  // n�s implicitamente numerados de 1 a nvs
  30.   int nvs, narcos;
  31. } GRAFO;
  32.  
  33. //--- prot�tipos das fun��es dispon�veis----------------------------
  34. //    ATEN��O AOS TIPOS DE ARGUMENTOS E DE RESULTADO
  35.  
  36.  
  37. GRAFO *new_graph(int nverts);
  38. /* cria um grafo com nverts vertices e sem arcos */
  39. void destroy_graph(GRAFO *g);
  40. /* liberta o espa�o reservado na cria��o do grafo */
  41. void insert_new_arc(int i, int j, GRAFO *g);
  42. /* insere arco (i,j) no grafo; n�o evita repeti��es */
  43. void remove_arc(ARCO *arco, int i, GRAFO *g);
  44. /* retira adjacente arco da lista de adjacentes de i */
  45. ARCO *find_arc(int i, int j, GRAFO *g);
  46. /* retorna um apontador para o arco (i,j) ou NULL se n�o existir */
  47.  
  48. //--- macros de acesso aos campos da estrutura --------------------------
  49.  
  50. #define NUM_VERTICES(g) ( (g) -> nvs )
  51. // numero de vertices
  52. #define NUM_ARCOS(g) ( (g) -> narcos )
  53. // numero de arcos
  54. #define ADJS_NO(i,g) ( (g) -> verts[i].adjs )
  55. // primeiro arco da lista de adjacentes do n� i
  56. #define PROX_ADJ(arco) ((arco) -> prox)
  57. // proximo adjacente
  58. #define ADJ_VALIDO(arco) (((arco) != NULL))
  59. // se arco � v�lido
  60. #define EXTREMO_FINAL(arco) ((arco) -> no_final)
  61. // qual o extremo final de arco
  62.  
  63.  
  64. //======  prot�tipos de fun��es auxiliares (privadas) ======
  65. static ARCO* cria_arco(int);
  66. static void free_arcs(ARCO *);
  67.  
  68.  
  69. //======  Implementa��o (defini��o das fun��es) ========================
  70.  
  71. // para criar um grafo com nverts vertices e sem ramos
  72. GRAFO *new_graph(int nverts)
  73. {
  74.   if (nverts > MAXVERTS) {
  75.     fprintf(stderr,"Erro: %d > MAXVERTS\n",nverts);
  76.     exit(EXIT_FAILURE);
  77.   }
  78.   GRAFO *g = (GRAFO *) malloc(sizeof(GRAFO));
  79.   if (g == NULL) {
  80.     fprintf(stderr,"Erro: falta memoria\n");
  81.     exit(EXIT_FAILURE);
  82.   }
  83.  
  84.   NUM_VERTICES(g) = nverts;  
  85.   NUM_ARCOS(g) = 0;
  86.   while (nverts) {
  87.     ADJS_NO(nverts,g) = NULL;
  88.     nverts--;
  89.   }
  90.   return g;
  91. }
  92.  
  93.  
  94. // para destruir um grafo criado
  95. void destroy_graph(GRAFO *g)
  96. { int i;
  97.   if (g != NULL) {
  98.     for (i=1; i<= NUM_VERTICES(g); i++)
  99.       free_arcs(ADJS_NO(i,g));
  100.     free(g);
  101.   }
  102. }
  103.  
  104. // para inserir um novo arco num grafo
  105. void insert_new_arc(int i, int j, GRAFO *g)
  106. { /* insere arco (i,j) no grafo g  */
  107.  
  108.   ARCO *arco = cria_arco(j);
  109.   PROX_ADJ(arco) = ADJS_NO(i,g);
  110.   ADJS_NO(i,g) = arco;  // novo adjacente fica � cabe�a da lista
  111.   NUM_ARCOS(g)++;
  112. }
  113.  
  114. // para remover um arco de um grafo (se existir na lista de adjs[i])
  115. void remove_arc(ARCO *arco, int i, GRAFO *g)
  116. {
  117.   if (arco != NULL) {
  118.     ARCO *aux = ADJS_NO(i,g), *prev = NULL;
  119.     while (aux != arco && ADJ_VALIDO(aux)) {
  120.       prev = aux;
  121.       aux = PROX_ADJ(aux);
  122.     }
  123.     if (aux == arco) {
  124.       if (prev == NULL) {
  125.     ADJS_NO(i,g)  = PROX_ADJ(arco);
  126.       } else PROX_ADJ(prev) = PROX_ADJ(arco);
  127.       free(arco);
  128.       NUM_ARCOS(g)--;
  129.     }
  130.   }
  131. }
  132.  
  133. // retorna um apontador para o arco (i,j) ou NULL se n�o existir
  134. ARCO *find_arc(int i, int j, GRAFO *g){
  135.   ARCO *adj = ADJS_NO(i,g);
  136.  
  137.   while(adj != NULL && EXTREMO_FINAL(adj) != j)
  138.     adj = PROX_ADJ(adj);
  139.  
  140.   return adj;
  141. }
  142.    
  143.  
  144. // ----  as duas funcoes abaixo sao auxiliares nao publicas ----
  145.  
  146. // reservar memoria para um novo arco e inicializa-lo
  147. static ARCO *cria_arco(int j)
  148. { // cria um novo adjacente
  149.   ARCO *arco = (ARCO *) malloc(sizeof(ARCO));
  150.   if (arco == NULL) {
  151.     fprintf(stderr,"ERROR: cannot create arc\n");
  152.     exit(EXIT_FAILURE);
  153.   }
  154.   EXTREMO_FINAL(arco) = j;
  155.   PROX_ADJ(arco) = NULL;
  156.   return arco;
  157. }
  158.  
  159. // libertar uma lista de arcos
  160. static void free_arcs(ARCO *arco)
  161. { // liberta lista de adjacentes
  162.   if (arco == NULL) return;
  163.   free_arcs(PROX_ADJ(arco));
  164.   free(arco);
  165. }
  166.  
  167. /*--------------------------------------------------------------------\
  168. | Defini��o de um tipo abstracto de dados QUEUE:                      |
  169. |   filas  (FIFO) com valores do tipo int                             |
  170. |                                                                     |
  171. |   A.P.Tom�s, CC211 (material para prova pratica), DCC-FCUP, 2012    |
  172. |   Last modified: 2012.12.28                                         |
  173. \--------------------------------------------------------------------*/
  174.  
  175.  
  176.  
  177. typedef enum {FALSE,TRUE} BOOL;
  178.  
  179.  
  180. typedef struct fila {
  181.   int inicio, fim, nmax;
  182.   int *queue;
  183. } QUEUE;
  184.  
  185.  
  186. // criar fila com capacidade para n inteiros
  187. QUEUE *mk_empty_queue(int n);
  188. // colocar valor na fila
  189. void enqueue(int v,QUEUE *f);
  190. // retirar valor na fila
  191. int dequeue(QUEUE *f);
  192. // verificar se a fila est� vazia
  193. BOOL queue_is_empty(QUEUE *f);
  194. // verificar se a fila n�o admite mais elementos
  195. BOOL queue_is_full(QUEUE *f);
  196. // liberta fila
  197. void free_queue(QUEUE *f);
  198.  
  199.  
  200. //-------------- Implementa��o ---------------------------------------
  201.  
  202.  
  203.  
  204.  
  205. // funcao auxiliar (privada)
  206.  
  207. static void queue_exit_error(char *msg);
  208.  
  209. static void queue_exit_error(char *msg)
  210. {
  211.   fprintf(stderr,"Error: %s.\n",msg);
  212.   exit(EXIT_FAILURE);
  213. }
  214.  
  215.  
  216.  
  217.  
  218. // criar fila com capacidade para n inteiros
  219. QUEUE *mk_empty_queue(int n)
  220. {
  221.   QUEUE *q = (QUEUE *) malloc(sizeof(QUEUE));
  222.   if (q == NULL)
  223.     queue_exit_error("sem memoria");
  224.  
  225.   q -> queue =  (int *) malloc(sizeof(int)*n);
  226.   if (q -> queue == NULL)
  227.     queue_exit_error("sem memoria");
  228.  
  229.   q -> nmax = n;
  230.   q -> inicio = -1;
  231.   q -> fim = 0;
  232.   return q;
  233. }
  234.  
  235. // libertar fila
  236. void free_queue(QUEUE *q)
  237. {
  238.   if (q != NULL) {
  239.     free(q -> queue);
  240.     free(q);
  241.   } else
  242.     queue_exit_error("fila mal construida");
  243. }
  244.  
  245.  
  246. // colocar valor na fila
  247. void enqueue(int v,QUEUE *q)
  248. {  
  249.   if (queue_is_full(q) == TRUE)
  250.     queue_exit_error("fila sem lugar");
  251.  
  252.   if (q -> queue == NULL)
  253.     queue_exit_error("fila mal construida");
  254.  
  255.   if (queue_is_empty(q)==TRUE)
  256.     q -> inicio = q -> fim; // fila fica com um elemento
  257.   q -> queue[q->fim] = v;
  258.   q -> fim = (q -> fim+1)%(q->nmax);
  259. }
  260.  
  261. // retirar valor na fila
  262. int dequeue(QUEUE *q)
  263. {  
  264.   int aux;
  265.   if (queue_is_empty(q) == TRUE)
  266.     queue_exit_error("fila sem valores");
  267.  
  268.   if (q -> queue == NULL)
  269.     queue_exit_error("fila mal construida");
  270.  
  271.   aux = q ->queue[q ->inicio];
  272.   q -> inicio = (q -> inicio+1)%(q -> nmax);
  273.   if (q -> inicio ==  q -> fim) {  // se s� tinha um elemento
  274.     q -> inicio = -1; q -> fim = 0;  
  275.   }
  276.   return aux;
  277. }
  278.  
  279. // verificar se a fila est� vazia
  280. BOOL queue_is_empty(QUEUE *q)
  281. {
  282.   if (q == NULL)
  283.     queue_exit_error("fila mal construida");
  284.  
  285.   if (q -> inicio == -1) return TRUE;
  286.   return FALSE;
  287. }
  288.  
  289. // verificar se a fila n�o admite mais elementos
  290. BOOL queue_is_full(QUEUE *q)
  291. {
  292.   if (q == NULL)
  293.     queue_exit_error("fila mal construida");
  294.  
  295.   if (q -> fim == q -> inicio) return TRUE;
  296.   return FALSE;
  297. }
  298.  
  299.  
  300.  
  301.  
  302. int bfs(GRAFO* grafo, int no) {
  303.     int vertices = NUM_VERTICES(grafo);
  304.  
  305.     QUEUE *fila = mk_empty_queue(vertices);
  306.  
  307.     int visitados[vertices+1], i;
  308.  
  309.     for(i=1; i<=vertices; i++) {
  310.         visitados[i] = FALSE;
  311.         //pai[i] = -1;
  312.     }
  313.  
  314.     enqueue(no,fila);
  315.     //pai[no]=-1;
  316.     visitados[no] = TRUE;
  317.  
  318.     int max = no;
  319.  
  320.     while(!queue_is_empty(fila)) {
  321.         int v = dequeue(fila);
  322.         ARCO *a = ADJS_NO(v,grafo);
  323.  
  324.         if(v>max)
  325.             max = v;
  326.  
  327.         while(a != NULL) {
  328.             int w = EXTREMO_FINAL(a);
  329.             if(!visitados[w]) {
  330.                 //pai[w] = v;
  331.                 visitados[w] = TRUE;
  332.                 enqueue(w,fila);
  333.             }
  334.             a = PROX_ADJ(a);
  335.         }
  336.     }
  337.     free_queue(fila);
  338.     return max;      
  339. }
  340.  
  341. int main () {
  342.     int nos, ramos,a,b,i,q, no;
  343.     scanf("%d %d", &nos, &ramos);
  344.  
  345.     int final[nos+1];
  346.  
  347.     GRAFO *grafo = new_graph(nos);
  348.  
  349.    
  350.  
  351.     for(i=0; i<ramos; i++) {
  352.         scanf("%d %d", &a,&b);
  353.         insert_new_arc(a,b,grafo);
  354.         insert_new_arc(b,a,grafo);
  355.     }
  356.  
  357.  
  358.     scanf("%d", &q);
  359.  
  360.     for(i=1; i<=nos; i++) {
  361.         final[i] = 0;
  362.     }
  363.  
  364.     for(i=0; i<q; i++) {
  365.         scanf("%d", &no);
  366.         if(final[no]== 0)
  367.             final[no] = bfs(grafo, no);
  368.  
  369.         printf("No %d: %d\n", no,final[no]);    
  370.     }
  371. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top