Advertisement
meriellez

Untitled

May 22nd, 2017
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.47 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. vector< vector<int> > g, gr;
  6. vector<char> used;
  7. vector<int> order, component;
  8.  
  9. void dfs1(int v) {
  10. used[v] = true;
  11. for (size_t i = 0; i < g[v].size(); i++)
  12. if (!used[ g[v][i] ])
  13. dfs1( g[v][i] );
  14. order.push_back(v);
  15. }
  16.  
  17. void dfs2(int v) {
  18. used[v] = true;
  19. component.push_back(v);
  20. for (size_t i = 0; i < gr[v].size(); i++)
  21. if (!used[ gr[v][i] ])
  22. dfs2( gr[v][i] );
  23. }
  24.  
  25. int main() {
  26. int n, m;
  27. cin >> n >> m;
  28. g.assign(n, vector<int>());
  29. gr.assign(n, vector<int>());
  30. for (int i = 0; i < m; i++) {
  31. int v, u;
  32. cin >> v >> u;
  33. v--; u--;
  34. g[v].push_back(u);
  35. gr[u].push_back(v);
  36. }
  37.  
  38. used.assign(n, false);
  39. for (int i = 0; i < n; i++)
  40. if (!used[i])
  41. dfs1(i);
  42.  
  43. int count = 0;
  44. used.assign(n, false);
  45. for (int i = 0; i < n; i++) {
  46. int v = order[n-1-i];
  47. if (!used[v]) {
  48. dfs2(v);
  49. if (component.size() > 0) {
  50. count++;
  51. }
  52. component.clear();
  53. }
  54. }
  55. cout << count;
  56. return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement