Advertisement
heian

Untitled

Jun 9th, 2019
145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.54 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. int N,M;
  7. bool viz[1001];
  8. int a[1001][1001];
  9.  
  10. /**
  11. Se da un graf neoirentat.
  12. Sa se spuna cate componente conexe are.
  13.  
  14.  
  15. Se vor citi din fisier:
  16. N = numarul de noduri(varfuri) din graf,
  17. numerotate de la 1 la n
  18. M = numarul de muchii din graf
  19. pe urmatoarele M linii se vor citi cate doua numere naturale,
  20. x y, cu semnificatia "exista muchie de la nodul x la nodul y"
  21. */
  22.  
  23.  
  24. ///depth first search
  25. ///parcurgere in adancime
  26. void DFS(int x)
  27. {
  28. int i,y,nr_vecini;
  29. viz[x] = true;
  30. nr_vecini = a[x][0];
  31. for(i=1;i<=nr_vecini;i++)
  32. {
  33. y = a[x][i];
  34. ///y este un vecin al lui x
  35. if(viz[y]==false)//daca y nu a fost inca vizitat
  36. DFS(y);
  37. }
  38. }
  39.  
  40. int main()
  41. {
  42. int i,x,y;
  43. ifstream fin("graf.in");
  44. fin>>N>>M;
  45.  
  46. ///In a[i][0] vom retine numarul de vecini ai nodului i
  47. for(i=1;i<=N;i++)
  48. {
  49. a[i][0] = 0;
  50. viz[i] = false;
  51. }
  52.  
  53. ///acum citim toate muchiile
  54. for(i=1;i<=M;i++)
  55. {
  56. fin>>x>>y;
  57. ///daca am fi folosit o matrice de adiacenta, am fi scris a[x][y] = 1; a[y][x] = 1;
  58. a[x][0]++;
  59. a[x][a[x][0]] = y;
  60. a[y][0]++;
  61. a[y][a[y][0]] = x;
  62. }
  63. fin.close();
  64.  
  65. ///SOLUTIE:
  66. int nr_componente_conexe=0;
  67. for(i=1;i<=N;i++)
  68. if(!viz[i])
  69. {
  70. DFS(i);
  71. nr_componente_conexe++;
  72. }
  73. cout<<nr_componente_conexe<<"\n";
  74. return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement