Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2020
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.01 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. using namespace std;
  5. int a[101][101], n,m,succ[101], pred[101],ctc[101],nrctc;
  6. void citire()
  7. {
  8. int i,x,y;
  9. cin>>n>>m;
  10. for(i=1; i<=m; i++)
  11. {
  12. cin>>x>>y;
  13. a[x][y]=1;
  14. }
  15. }
  16. void DFS1(int start)
  17. {
  18. succ[start]=1;
  19. for(int i=1; i<=n; i++)
  20. {
  21. if(a[start][i] and !succ[i])
  22. DFS1(i);
  23. }
  24.  
  25. }
  26. void DFS(int start)
  27. {
  28. pred[start]=1;
  29. for(int i=1; i<=n; i++)
  30. {
  31. if(a[i][start] and !pred[i])
  32. DFS(i);
  33. }
  34.  
  35. }
  36. void componente()
  37. {
  38. for(int i=1; i<=n; i++)
  39. {
  40. if(ctc[i]==0)
  41. {
  42. DFS1(i); DFS(i);
  43. nrctc++;
  44. for(int j=1; j<=n; j++)
  45. {
  46. if(succ[j] && pred[j])
  47. ctc[j]=nrctc;
  48. succ[j]=0; pred[j]=0;
  49. }
  50. }
  51.  
  52. }
  53. }
  54. int main()
  55. {
  56. citire();
  57. componente();
  58. cout<<nrctc;
  59. return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement