Guest User

Untitled

a guest
Mar 17th, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.07 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector < int > G[100005], rev[100005], dag[100005], order;
  4. int N, M;
  5. int A[100005], B[100005];
  6. bool flag[100005] = {};
  7. int cmp[100005];
  8. int cnt[100005] = {};
  9.  
  10. void dfs(int v)
  11. {
  12. if(flag[v]) return;
  13. flag[v] = true;
  14. for(int i = 0; i < G[v].size(); i++) dfs(G[v][i]);
  15. order.push_back(v);
  16. return;
  17. }
  18.  
  19. void rdfs(int v, int k)
  20. {
  21. if(~cmp[v]) return;
  22. cmp[v] = k;
  23. for(int i = 0; i < rev[v].size(); i++) rdfs(rev[v][i], k);
  24. return;
  25. }
  26.  
  27. int main()
  28. {
  29. cin >> N >> M;
  30. for(int i = 0; i < M; i++) {
  31. cin >> A[i] >> B[i]; --A[i], --B[i];
  32. G[A[i]].push_back(B[i]);
  33. rev[B[i]].push_back(A[i]);
  34. }
  35.  
  36. for(int i = 0; i < N; i++) dfs(i);
  37. int n = 0;
  38. fill_n(cmp, 100005, -1);
  39. for(int i = N - 1; i >= 0; i--) {
  40. if(!~cmp[order[i]]) {
  41. rdfs(order[i], n); n++;
  42. }
  43. }
  44. for(int i = 0; i < M; i++) if(cmp[A[i]] != cmp[B[i]]) cnt[cmp[B[i]]]++;
  45. int ans = 0;
  46. for(int i = 0; i < n; i++) {
  47. if(cnt[i] == 0) ans++;
  48. }
  49. cout << ans << endl;
  50. return (0);
  51. }
Add Comment
Please, Sign In to add comment