Advertisement
Aniebunny

componente tare conexe

Oct 21st, 2019
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4. ifstream f("matrice.txt");
  5. int a[10][10],n,m,x,y,s,suc[100],pred[100],nrc;
  6. void citire()
  7. {
  8. f>>n>>m;
  9. for(int i=1;i<=m;i++)
  10. {
  11. f>>x>>y;
  12. a[x][y]=1;
  13. }
  14. }
  15. void afisare()
  16. {
  17. for(int i=1;i<=n;i++)
  18. {
  19. for(int j=1;j<=n;j++)
  20. cout<<a[i][j]<<" ";
  21. cout<<endl;
  22. }
  23. }
  24. void dfsuc(int nod)
  25. {
  26. int k;
  27. suc[nod]=nrc;
  28. for(k=1;k<=n;k++)
  29. if(a[nod][k]==1&&suc[k]==0)
  30. dfsuc(k);
  31. }
  32. void dfpred(int nod)
  33. {
  34. int k;
  35. pred[nod]=nrc;
  36. for(k=1;k<=n;k++)
  37. if(a[k][nod]==1&&pred[k]==0)
  38. dfpred(k);
  39. }
  40. int main()
  41. { citire();
  42. afisare();
  43. nrc=1;
  44. for(int i=1;i<=n;i++)
  45. if(suc[i]==0)
  46. {
  47. dfsuc(i);
  48. dfpred(i);
  49. for(int j=1;j<=n;j++)
  50. if(suc[j]!=pred[j]) suc[j]=pred[j]=0;
  51. nrc++;
  52. }
  53. for(int i=1;i<nrc;i++)
  54. {
  55. cout<<"componenta tare conexa "<<i<<":"<<endl;
  56. for(int j=1;j<=n;j++)
  57. if(suc[j]==i) cout<<j<<" ";
  58. cout<<endl;
  59. }
  60. return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement