Advertisement
Guest User

Untitled

a guest
Feb 24th, 2020
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.20 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. #include <stack>
  4. using namespace std;
  5. ifstream cin("nuclee.in");
  6. ofstream cout("nuclee.out");
  7.  
  8. using VI = vector<int>;
  9. using VVI = vector<VI>;
  10. using VB = vector<bool>;
  11.  
  12. stack<int>stk;
  13.  
  14. int n, m,c,N, k;
  15.  
  16. VVI G;
  17. VI l, niv;
  18. VB v, inStack;
  19.  
  20.  
  21. void tarjan(int x)
  22. {
  23. l[x] = niv[x] = ++c;
  24. stk.push(x);
  25. inStack[x] = v[x] = true;
  26.  
  27. for(const int&y : G[x])
  28. {
  29. if(!v[y])
  30. {
  31. tarjan(y);
  32. l[x] = min(l[x],l[y]);
  33. }
  34. else
  35. if(inStack[y])
  36. l[x] = min(l[x],niv[y]);
  37. }
  38.  
  39. if(l[x] == niv[x])
  40. {
  41. N++;
  42. while (true)
  43. {
  44. int y = stk.top();
  45. stk.pop();
  46. inStack[y] = false;
  47. if (y == x)
  48. break;
  49. }
  50. }
  51. }
  52.  
  53. int main()
  54. {
  55. cin >> n;
  56. G = VVI(n+1);
  57. v = inStack = VB(n+1);
  58. l = niv = VI(n+1);
  59.  
  60. for(int i=1; i<=n; i++)
  61. {
  62. cin >> k;
  63. while(k--)
  64. {
  65. int x;
  66. cin >> x;
  67. G[i].push_back(x);
  68. }
  69. }
  70.  
  71. for(int i=1; i<=n; i++)
  72. if(!v[i])
  73. tarjan(i);
  74.  
  75. cout << N;
  76.  
  77. return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement