Advertisement
Guest User

Untitled

a guest
Mar 30th, 2020
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.36 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. ifstream fin("componenteconexe2.in");
  6. ofstream fout("componenteconexe2.out");
  7.  
  8. struct nod{
  9. int valoare;
  10. nod *urmator;
  11. }*prim[100001];
  12.  
  13.  
  14. long long n,m,coada[100001],vizitat[100001],c;
  15.  
  16. void adaugare_in_lista(nod *&prim,long long x)
  17. {
  18. nod *q = new nod;
  19. q->valoare = x;
  20. q->urmator = prim;
  21. prim = q;
  22. }
  23.  
  24. void citire()
  25. {
  26. fin>>n;
  27. long long i,x,y;
  28. while(fin>>x>>y)
  29. {
  30. adaugare_in_lista(prim[x],y);
  31. adaugare_in_lista(prim[y],x);
  32. m++;
  33. }
  34. }
  35.  
  36.  
  37. void BFS(long long nod_start,long long &componenta_conexa)
  38. {
  39. long long p,u,i,x;
  40. p=u=0;
  41. vizitat[nod_start] = componenta_conexa;
  42. coada[u] = nod_start;
  43. while(p<=u)
  44. {
  45. x = coada[p++];
  46. for(nod *q = prim[x];q;q=q->urmator)
  47. if(vizitat[q->valoare] == 0)
  48. {
  49. coada[++u] = q->valoare;
  50. vizitat[q->valoare] = componenta_conexa;
  51. }
  52. }
  53. m = m-u;
  54.  
  55. }
  56. int main()
  57. {
  58. citire();
  59. long long componenta_conexa ,i;
  60. componenta_conexa = 0;
  61. for(i=1;i<=n;i++)
  62. if(vizitat[i]==0)
  63. {
  64. componenta_conexa = componenta_conexa + 1;
  65. BFS(i,componenta_conexa);
  66. }
  67. fout<<m;
  68. fin.close();
  69. fout.close();
  70. return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement