fork(2) download 
  1. /**
  2. 	Template by proptit_4t41
  3. 	Applied for C++11/C++14 (Add -std=c++14 to your IDE.)
  4. 	To make it compatible to C++98, remove all tuple typedefs,
  5. 	unordered sets/maps/multisets/multimaps, and add a space
  6. 	between two '<'/'>'s when declaring multi-dimensional vectors.
  7. **/
  8.  
  9. /**
  10. 	code written by a random fan of momocashew
  11. 	world.execute(me);
  12. **/
  13.  
  14. #include <bits/stdc++.h>
  15. using namespace std;
  16.  
  17. /** -----BASIC MACROES----- **/
  18. #define endl '\n'
  19. #define i64 long long
  20. #define u64 unsigned long long
  21. #define ld long double
  22. #define pub push_back
  23. #define puf push_front
  24. #define pob pop_back
  25. #define pof pop_front
  26. #define mmap multimap
  27. #define mset multiset
  28. #define umap unordered_map
  29. #define uset unordered_set
  30. #define ummap unordered_multimap
  31. #define umset unordered_multiset
  32. #define mp make_pair
  33. #define mt make_tuple
  34. #define fi first
  35. #define se second
  36. #define REcheck cout << "RE here?\n"
  37. #define tracker1(i) cout << "working at " << i << endl;
  38. #define tracker2(i,j) cout << "working at " << i << "-" << j << endl;
  39. #define tracker3(i,j,k) cout << "working at " << i << "-" << j << "-" << k << endl;
  40. const long double PI = 3.14159265358979323846264338327950288419716939937510582097494459230;
  41. const long long MOD = 1000000007LL;
  42. const long long INF = 1e9;
  43. const long long LINF = 1e18;
  44. const long double EPS = 1e-9;
  45. const long double GOLD = ((1+sqrt(5))/2);
  46. typedef vector<i64> vi;
  47. typedef stack<i64> si;
  48. typedef queue<i64> qi;
  49. typedef vector<vector<i64>> vvi;
  50. typedef vector<ld> vd;
  51. typedef vector<vector<ld>> vvd;
  52. typedef vector<string> vs;
  53. typedef vector<bool> vb;
  54. typedef pair<i64, i64> pii;
  55. typedef pair<i64, pii> pip;
  56. typedef pair<pii, i64> ppi;
  57. typedef tuple<i64, i64> tii;
  58. typedef tuple<i64, i64, i64> tiii;
  59. typedef vector<pii> vp;
  60.  
  61. /** -----BIT CONTROLS----- **/
  62. template<class T> int getbit(T s, int i) { return (s >> 1) & 1; }
  63. template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
  64. template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
  65. template<class T> int cntbit(T s) { return __builtin_popcount(s); }
  66.  
  67. /** -----IDEAS/ALGORITHMS-----
  68.  
  69.     -------------------------- **/
  70.  
  71. /// MAIN SOLUTION STARTS HERE
  72.  
  73. /** -----CUSTOM TYPEDEFS----- **/
  74.  
  75.  
  76. /** -----GLOBAL VARIABLES----- **/
  77. //int T, cas = 0; // for multi-testcase problems
  78. i64 n, m, scc = 0; si s;
  79. vvi adj1, adj2; vb visited;
  80.  
  81. /** -----EXTENSIVE FUNCTIONS----- **/
  82. void firstDFS(i64 z) {
  83. 	visited[z] = true;
  84. 	for (i64 i=0; i<adj1[z].size(); i++) {
  85. 		if (!visited[adj1[z][i]]) firstDFS(adj1[z][i]);
  86. 	}
  87. 	s.push(z);
  88. }
  89.  
  90. void secondDFS(i64 z) {
  91. 	visited[z] = true;
  92. 	for (i64 i=0; i<adj2[z].size(); i++) {
  93. 		if (!visited[adj2[z][i]]) secondDFS(adj2[z][i]);
  94. 	}
  95. }
  96.  
  97. /** -----COMPULSORY FUNCTIONS----- **/
  98. void VarInput() {
  99. 	//cin >> T; // for multi-testcase problems
  100. 	cin >> n >> m;
  101. 	adj1.resize(n+1, vi(0)); adj2.resize(n+1, vi(0));
  102. 	visited.resize(n+1, false);
  103. 	while (m--) {
  104. 		i64 a, b; cin >> a >> b;
  105. 		adj1[a].pub(b); adj2[b].pub(a);
  106. 	}
  107. }
  108.  
  109. void ProSolve() {
  110. 	//cout << "Case " << ++cas << ": " << ans << endl; // for multi-testcase problems
  111. 	for (i64 i=1; i<=n; i++) {
  112. 		if (!visited[i]) firstDFS(i);
  113. 	}
  114. 	for (i64 i=1; i<=n; i++) visited[i] = false;
  115. 	while (!s.empty()) {
  116. 		i64 z = s.top(); s.pop();
  117. 		if (!visited[z]) {
  118. 			scc++; secondDFS(z);
  119. 		}
  120. 	}
  121. 	cout << scc;
  122. }
  123.  
  124. /** -----MAIN FUNCTION----- **/
  125. int main() {
  126. 	//freopen("FILE.INP", "r", stdin);
  127. 	//freopen("FILE.OUT", "w", stdout);
  128. 	ios_base::sync_with_stdio(0); cin.tie(NULL);
  129. 	VarInput();
  130. 	//while(T--) ProSolve(); // for multi-testcase problems
  131. 	ProSolve(); // for regular problems
  132. 	return 0;
  133. }
Success #stdin #stdout 0s 4364KB
comments (?)
stdin 
8 14
1 2
2 3
3 1
4 2
4 3
4 5
5 4
5 6
6 3
6 7
7 6
8 5
8 6
8 8
stdout 
4
https://ideone.com/V7uTfX
VNSPOJ-TJALG (Kosaraju's Algorithm).
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!