Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2018
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.43 KB | None | 0 0
  1.  
  2. #include<stdio.h>
  3. #include<string.h>
  4. #include<stdlib.h>
  5. #include<ctype.h>
  6. #include<stdbool.h>
  7. #define INFINI 10000000
  8.  
  9. struct graphs{
  10. int sons[1001];
  11. int nbrofsons;
  12. int value;
  13. };
  14. typedef struct graphs graphs;
  15. graphs tab[1001];
  16.  
  17. int noeudVisite[1001];
  18. const int NON_VISITE = 0;
  19. const int DEJA_VISITE = 1;
  20. const int EN_COURS_DE_VISITE = 2;
  21. bool res=false;
  22.  
  23. bool parcousprofondeur(int noeud)
  24. {
  25.  
  26. if(noeudVisite[noeud]== DEJA_VISITE)
  27. return false;
  28. if(noeudVisite[noeud]== EN_COURS_DE_VISITE)
  29. return true;
  30.  
  31. noeudVisite[noeud]=EN_COURS_DE_VISITE;
  32.  
  33. for(int i=0;i<tab[noeud].nbrofsons;i++)
  34.  
  35. if(parcousprofondeur(tab[noeud].sons[i]))
  36.  
  37.  
  38. return true;
  39.  
  40. noeudVisite[noeud ]=DEJA_VISITE;
  41. return false;
  42. // }
  43. //else {
  44. /*for(int i=0;i<1000;i++)
  45. deja[noeud]=true;
  46. res=true;
  47. //return res;
  48. // }
  49. //deja[noeud]=false;*/
  50. }
  51.  
  52. int main()
  53. {
  54. int nbrofnoeuds,nbrofrelation;
  55. scanf("%d %d",&nbrofnoeuds,&nbrofrelation);
  56.  
  57.  
  58.  
  59. for(int i=0;i<nbrofrelation;i++)
  60. {
  61. int postion,son;
  62. scanf("%d %d",&postion,&son);
  63.  
  64. tab[postion].sons[tab[postion].nbrofsons]=son;
  65. tab[postion].nbrofsons++;
  66. }
  67.  
  68. for (int noeud = 0; noeud < nbrofnoeuds; noeud++)
  69. res=res||parcousprofondeur(noeud);
  70.  
  71.  
  72. if(res)
  73. printf("OUI\n");
  74. else
  75. printf("NON\n");
  76.  
  77.  
  78.  
  79. return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement