Advertisement
Guest User

Untitled

a guest
Feb 24th, 2020
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.66 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int n, m, A[101][101], S[101], P[101], x, y, nc;
  6.  
  7. void DFS(int v, int c)
  8. {
  9. S[v]=c;
  10. for(int i=1;i<=n;i++)
  11. if(!S[i] && A[v][i]) DFS(i, c);
  12. }
  13.  
  14. void DFP(int v, int c)
  15. {
  16. P[v]=c;
  17. for(int i=1;i<=n;i++)
  18. if(!P[i] && A[i][v]) DFP(i, c);
  19. }
  20.  
  21. int main()
  22. {
  23. cin>>n>>m;
  24. for(int i=1;i<=m;i++)
  25. {
  26. cin>>x>>y;
  27. A[x][y]=1;
  28. }
  29. for(int i=1;i<=n;i++)
  30. if(!S[i])
  31. {
  32. nc++;
  33. DFS(i, nc); DFP(i, nc);
  34. for(int j=1;j<=n;j++)
  35. if(S[j]!=P[j]) P[j]=S[j]=0;
  36. }
  37. cout<<nc;
  38. return 0;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement