Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**------------------------
- Author : NikolaP
- Compiler : C++
- -------------------------*/
- //{ Setup
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long int ll;
- typedef long double ld;
- typedef vector<int> vi;
- const int inf = INT_MAX;
- const bool debug = 0;
- //}
- struct tarjan{
- int n,time;
- vector<vi> graph;
- tarjan(int _n,int m){
- n = _n;
- time = 0;
- graph.resize(n);
- for(int i = 0 ; i<m ; ++i){
- int from, to;
- cin >> from >> to;
- graph[from].push_back(to);
- }
- }
- void FindComponent(int idx, vi& disc, vi& low, stack<int>& s, vector<bool>& stackitem){
- disc[idx] = low[idx] = ++time;
- s.push(idx);
- stackitem[idx] = true;
- for(int i = 0; i < graph[idx].size(); ++i){
- int to = graph[idx][i];
- if(disc[to] == -1){
- FindComponent(to,disc,low,s,stackitem);
- low[idx] = min(low[idx], low[to]);
- }
- else if(stackitem[to]){
- low[idx] = min(low[idx],disc[to]);
- }
- }
- if(low[idx] == disc[idx]){
- while(s.top() != idx){
- int popped = s.top();
- cout << popped<< " ";
- stackitem[popped] = false;
- s.pop();
- }
- cout << s.top() << '\n';
- stackitem[s.top()] = false;
- s.pop();
- }
- }
- void SCC(){
- vi disc(n,-1),low(n,-1);
- vector<bool> stackitem(n,false);
- stack<int> s;
- for(int i = 0; i < n; ++i){
- if(disc[i] == -1) FindComponent(i,disc,low,s,stackitem);
- }
- }
- };
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.precision(8);
- //cout << fixed;
- int n,m;
- cin >> n >> m;
- tarjan t = tarjan(n,m);
- t.SCC();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment