API tools faq
paste
Advertisement
i_love_rao_khushboo

Untitled

i_love_rao_khushboo
Aug 21st, 2022 (edited)
1,175
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 12.97 KB | None | 0 0
raw download clone embed print report
  1. // Ref: https://cp-algorithms.com/graph/strongly-connected-components.html
  2.  
  3. /**********************************************************************************************************************/
  4.  
  5. // METHOD - 1
  6.  
  7. #include<bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define ll long long
  11. #define ld long double
  12. #define ull unsigned long long
  13. #define pb push_back
  14. #define ppb pop_back
  15. #define mp make_pair
  16. #define F first
  17. #define S second
  18. #define PI 3.1415926535897932384626
  19. #define sz(x) ((int)(x).size())
  20. #define vset(v, n, val) v.clear(); v.resize(n, val)
  21.  
  22. typedef pair<int, int> pii;
  23. typedef pair<ll, ll> pll;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vll;
  26. typedef vector<ull> vull;
  27. typedef vector<bool> vb;
  28. typedef vector<char> vc;
  29. typedef vector<string> vs;
  30. typedef vector<pii> vpii;
  31. typedef vector<pll> vpll;
  32. typedef vector<vi> vvi;
  33. typedef vector<vll> vvll;
  34. typedef vector<vull> vvull;
  35. typedef vector<vb> vvb;
  36. typedef vector<vc> vvc;
  37. typedef vector<vs> vvs;
  38.  
  39. /************************************************** DEBUGGER *******************************************************************************************************/
  40.  
  41. #ifndef ONLINE_JUDGE
  42. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  43. #else
  44. #define debug(x)
  45. #endif
  46.  
  47. void _print(ll t) { cerr << t; }
  48. void _print(int t) { cerr << t; }
  49. void _print(string t) { cerr << t; }
  50. void _print(char t) { cerr << t; }
  51. void _print(ld t) { cerr << t; }
  52. void _print(double t) { cerr << t; }
  53. void _print(ull t) { cerr << t; }
  54.  
  55. template <class T, class V> void _print(pair <T, V> p);
  56. template <class T> void _print(vector <T> v);
  57. template <class T> void _print(vector <vector<T>> v);
  58. template <class T> void _print(set <T> v);
  59. template <class T, class V> void _print(map <T, V> v);
  60. template <class T> void _print(multiset <T> v);
  61. template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.F); cerr << ","; _print(p.S); cerr << "}"; }
  62. template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  63. template <class T> void _print(vector <vector<T>> v) { cerr << "==>" << endl; for (vector<T> vec : v) { for(T i : vec) {_print(i); cerr << " "; } cerr << endl; } }
  64. template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  65. template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  66. template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) {_print(i); cerr << " "; } cerr << "]"; }
  67.  
  68. /*******************************************************************************************************************************************************************/
  69.  
  70. mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
  71. int rng(int lim) {
  72.     uniform_int_distribution<int> uid(0,lim-1);
  73.     return uid(rang);
  74. }
  75.  
  76. const int INF = 0x3f3f3f3f;
  77. const int mod = 1e9+7;
  78.  
  79. ll mod_exp(ll a, ll b) { a %= mod; if(a == 0) return 0LL; ll res = 1LL;
  80.                          while(b > 0) { if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }
  81.                          
  82. ll mod_inv(ll a) { return mod_exp(a, mod - 2); } // works only for prime value of "mod"
  83. ll GCD(ll a, ll b) { return (b == 0) ? a : GCD(b, a % b); }
  84.  
  85. /******************************************************************************************************************************/
  86.  
  87. const int N = 100005;
  88.  
  89. vi g[N]; // adjacency list representation of graph
  90. vi rg[N]; // to store the reverse graph
  91. vi vis(N); // visited array
  92. vi color(N); // to store the component of each vertex
  93.  
  94. // if there exists a path from vertex 'x' to 'y' in the DFS tree generated
  95. // of the original graph then in the order vector 'y' must come before 'x'
  96. vi order;
  97.  
  98. void dfs(int curr) {
  99.     vis[curr] = 1;
  100.     for(auto x: g[curr]) {
  101.         if(!vis[x]) dfs(x);
  102.     }
  103.    
  104.     order.pb(curr);
  105. }
  106.  
  107. void dfs_reverse(int curr, int col) {
  108.     vis[curr] = 1;
  109.     color[curr] = col; // mark it with color
  110.     for(auto x: rg[curr]) {
  111.         if(!vis[x]) dfs_reverse(x, col);
  112.     }
  113. }
  114.  
  115. void solve()
  116. {
  117.     // n = #vertices, m = #edges
  118.     int n, m; cin >> n >> m;
  119.    
  120.     // vertices are 1-based indexed
  121.     for(int i = 0; i < m; i++) {
  122.         int x, y; cin >> x >> y;
  123.         g[x].pb(y); // store in graph
  124.         rg[y].pb(x); // store in reverse graph
  125.     }
  126.    
  127.     // mark all vertices as not visited initially
  128.     fill(vis.begin(), vis.end(), 0);
  129.    
  130.     // perform dfs on the original graph so as
  131.     // to construct the order vector
  132.     for(int vertex = 1; vertex <= n; vertex++) {
  133.         if(!vis[vertex]) {
  134.             dfs(vertex);
  135.         }
  136.     }
  137.    
  138.     // again perform dfs on the reverse graph to
  139.     // find out the strongly connected components
  140.     fill(vis.begin(), vis.end(), 0);
  141.    
  142.     // to mark the vertices belonging to the same SCC with
  143.     // the same color
  144.     int col = 1;
  145.    
  146.     // start from the last vertex of order vector
  147.     for(int i = n - 1; i >= 0; i--) {
  148.         if(!vis[order[i]]) {
  149.             dfs_reverse(order[i], col);
  150.             col++;
  151.         }
  152.     }
  153.  
  154.     // to find the #SCC
  155.     set<int> s;
  156.     for(int vertex = 1; vertex <= n; vertex++) {
  157.         s.insert(color[vertex]);
  158.     }
  159.    
  160.     cout << "SCC in the DG = " << s.size() << "\n";
  161. }
  162.  
  163. int main()
  164. {
  165.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  166.     srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  167.  
  168.     // #ifndef ONLINE_JUDGE
  169.     //     freopen("input.txt", "r", stdin);
  170.     //     freopen("output.txt", "w", stdout);
  171.     // #endif
  172.    
  173.     // #ifndef ONLINE_JUDGE
  174.     //      freopen("error.txt", "w", stderr);
  175.     // #endif
  176.    
  177.     int t = 1;
  178.     // int test = 1;
  179.     // cin >> t;
  180.     while(t--) {
  181.         // cout << "Case #" << test++ << ": ";
  182.         solve();
  183.     }
  184.  
  185.     return 0;
  186. }
  187.  
  188. /*
  189.  
  190. Sample i/p --->
  191.  
  192. 6 7
  193. 1 2
  194. 2 3
  195. 3 1
  196. 3 4
  197. 4 5
  198. 5 6
  199. 6 4
  200.  
  201. Sample o/p --->
  202.  
  203. SCC in the DG = 2
  204.  
  205. */
  206.  
  207. // Time complexity: O(|V| + |E|)
  208. // NOTE ---> It is worth mentioning the fact that the order vector represents reversed topological sort
  209. //           (vertices' sort by exit time) of the vertices of condensation graph.
  210. //           For more details of this statement, visit: https://cp-algorithms.com/graph/strongly-connected-components.html
  211.  
  212.  
  213. /**********************************************************************************************************/
  214.  
  215. // METHOD - 2
  216.  
  217. // Another implementation to store the vertices of same SCC together
  218. // Below code is exactly same as above except the use of in_comp[] instead of color vector
  219.  
  220. #include<bits/stdc++.h>
  221. using namespace std;
  222.  
  223. #define ll long long
  224. #define ld long double
  225. #define ull unsigned long long
  226. #define pb push_back
  227. #define ppb pop_back
  228. #define mp make_pair
  229. #define F first
  230. #define S second
  231. #define PI 3.1415926535897932384626
  232. #define sz(x) ((int)(x).size())
  233. #define vset(v, n, val) v.clear(); v.resize(n, val)
  234.  
  235. typedef pair<int, int> pii;
  236. typedef pair<ll, ll> pll;
  237. typedef vector<int> vi;
  238. typedef vector<ll> vll;
  239. typedef vector<ull> vull;
  240. typedef vector<bool> vb;
  241. typedef vector<char> vc;
  242. typedef vector<string> vs;
  243. typedef vector<pii> vpii;
  244. typedef vector<pll> vpll;
  245. typedef vector<vi> vvi;
  246. typedef vector<vll> vvll;
  247. typedef vector<vull> vvull;
  248. typedef vector<vb> vvb;
  249. typedef vector<vc> vvc;
  250. typedef vector<vs> vvs;
  251.  
  252. /************************************************** DEBUGGER *******************************************************************************************************/
  253.  
  254. #ifndef ONLINE_JUDGE
  255. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  256. #else
  257. #define debug(x)
  258. #endif
  259.  
  260. void _print(ll t) { cerr << t; }
  261. void _print(int t) { cerr << t; }
  262. void _print(string t) { cerr << t; }
  263. void _print(char t) { cerr << t; }
  264. void _print(ld t) { cerr << t; }
  265. void _print(double t) { cerr << t; }
  266. void _print(ull t) { cerr << t; }
  267.  
  268. template <class T, class V> void _print(pair <T, V> p);
  269. template <class T> void _print(vector <T> v);
  270. template <class T> void _print(vector <vector<T>> v);
  271. template <class T> void _print(set <T> v);
  272. template <class T, class V> void _print(map <T, V> v);
  273. template <class T> void _print(multiset <T> v);
  274. template <class T, class V> void _print(pair <T, V> p) { cerr << "{"; _print(p.F); cerr << ","; _print(p.S); cerr << "}"; }
  275. template <class T> void _print(vector <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  276. template <class T> void _print(vector <vector<T>> v) { cerr << "==>" << endl; for (vector<T> vec : v) { for(T i : vec) {_print(i); cerr << " "; } cerr << endl; } }
  277. template <class T> void _print(set <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  278. template <class T> void _print(multiset <T> v) { cerr << "[ "; for (T i : v) {_print(i); cerr << " "; } cerr << "]"; }
  279. template <class T, class V> void _print(map <T, V> v) { cerr << "[ "; for (auto i : v) {_print(i); cerr << " "; } cerr << "]"; }
  280.  
  281. /*******************************************************************************************************************************************************************/
  282.  
  283. mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
  284. int rng(int lim) {
  285.     uniform_int_distribution<int> uid(0,lim-1);
  286.     return uid(rang);
  287. }
  288.  
  289. const int INF = 0x3f3f3f3f;
  290. const int mod = 1e9+7;
  291.  
  292. ll mod_exp(ll a, ll b) { a %= mod; if(a == 0) return 0LL; ll res = 1LL;
  293.                          while(b > 0) { if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }
  294.                          
  295. ll mod_inv(ll a) { return mod_exp(a, mod - 2); } // works only for prime value of "mod"
  296. ll GCD(ll a, ll b) { return (b == 0) ? a : GCD(b, a % b); }
  297.  
  298. /******************************************************************************************************************************/
  299.  
  300. const int N = 100005;
  301.  
  302. vi g[N]; // adjacency list representation of graph
  303. vi rg[N]; // to store the reverse graph
  304. vi vis(N); // visited array
  305.  
  306. // to store the component of each vertex
  307. // in_comp[i] stores all the vertices in the ith component
  308. vi in_comp[N];
  309.  
  310. // if there exists a path from vertex 'x' to 'y' in the DFS tree generated
  311. // of the original graph then in the order vector 'y' must come before 'x'
  312. vi order;
  313.  
  314. void dfs(int curr) {
  315.     vis[curr] = 1;
  316.     for(auto x: g[curr]) {
  317.         if(!vis[x]) dfs(x);
  318.     }
  319.    
  320.     order.pb(curr);
  321. }
  322.  
  323. void dfs_reverse(int curr, int col) {
  324.     vis[curr] = 1;
  325.     in_comp[col].pb(curr); // put it in the component
  326.     for(auto x: rg[curr]) {
  327.         if(!vis[x]) dfs_reverse(x, col);
  328.     }
  329. }
  330.  
  331. void solve()
  332. {
  333.     // n = #vertices, m = #edges
  334.     int n, m; cin >> n >> m;
  335.    
  336.     // vertices are 1-based indexed
  337.     for(int i = 0; i < m; i++) {
  338.         int x, y; cin >> x >> y;
  339.         g[x].pb(y); // store in graph
  340.         rg[y].pb(x); // store in reverse graph
  341.     }
  342.    
  343.     // mark all vertices as not visited initially
  344.     fill(vis.begin(), vis.end(), 0);
  345.    
  346.     // perform dfs on the original graph so as
  347.     // to construct the order vector
  348.     for(int vertex = 1; vertex <= n; vertex++) {
  349.         if(!vis[vertex]) {
  350.             dfs(vertex);
  351.         }
  352.     }
  353.    
  354.     // again perform dfs on the reverse graph to
  355.     // find out the strongly connected components
  356.     fill(vis.begin(), vis.end(), 0);
  357.    
  358.     // to mark the vertices belonging to the same SCC with
  359.     // the same color
  360.     int col = 1;
  361.    
  362.     // start from the last vertex of order vector
  363.     for(int i = n - 1; i >= 0; i--) {
  364.         if(!vis[order[i]]) {
  365.             dfs_reverse(order[i], col);
  366.            
  367.             if(in_comp[col].size() > 0) {
  368.                 cout << "Vertices in the same SCC = ";
  369.                 for(auto it = in_comp[col].begin(); it != in_comp[col].end(); it++) {
  370.                     cout << *it << " ";
  371.                 }
  372.                
  373.                 cout << "\n";
  374.             }
  375.            
  376.             col++;
  377.         }
  378.     }
  379. }
  380.  
  381. int main()
  382. {
  383.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  384.     srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  385.  
  386.     // #ifndef ONLINE_JUDGE
  387.     //     freopen("input.txt", "r", stdin);
  388.     //     freopen("output.txt", "w", stdout);
  389.     // #endif
  390.    
  391.     // #ifndef ONLINE_JUDGE
  392.     //      freopen("error.txt", "w", stderr);
  393.     // #endif
  394.    
  395.     int t = 1;
  396.     // int test = 1;
  397.     // cin >> t;
  398.     while(t--) {
  399.         // cout << "Case #" << test++ << ": ";
  400.         solve();
  401.     }
  402.  
  403.     return 0;
  404. }
  405.  
  406. /*
  407.  
  408. Sample i/p --->
  409.  
  410. 6 7
  411. 1 2
  412. 2 3
  413. 3 1
  414. 3 4
  415. 4 5
  416. 5 6
  417. 6 4
  418.  
  419. Sample o/p --->
  420.  
  421. Vertices in the same SCC = 1 3 2
  422. Vertices in the same SCC = 4 6 5
  423.  
  424. */
  425.  
  426. /* # Code for finding out all the vertices of all SSC can also be found here:
  427.      https://cp-algorithms.com/graph/strongly-connected-components.html
  428.  
  429.    # Another interesting question on this topic:
  430.      https://cses.fi/problemset/task/1682/
  431. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!