Cod sursa(job #2159505)

Utilizator OpportunityVlad Negura Opportunity Data 10 martie 2018 23:22:05
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(false);cout.precision(30);cout.tie(0);cin.tie(0);
#define ll long long
#define ld long double
#define rep(i, a, b) for(__typeof(b)i=(a)-((a)>(b));i!=(b)-((a)>(b));i+=1-2*((a)>(b)))
#define whilet() ll t;cin>>t;while(t--)
#define all(c) (c).begin(), (c).end()

ifstream fi("/home/keloo/Projects/algorithms/ctc.in");
ofstream fo("/home/keloo/Projects/algorithms/ctc.out");

int n,m,x,y,idx[100001],idxc=1,in[100001],low[100001];
vector<int> g[100001],con;
vector<vector<int>> scc;
stack<int> s;

void tarjan(const int n, const vector <int>* adj)
{
    idx[n] = low[n] = idxc;
    idxc ++;
    s.push(n), in[n] = 1;

    vector <int>::const_iterator it;
    for (it = adj[n].begin(); it != adj[n].end(); ++ it) {
        if (!idx[*it])
            tarjan(*it, adj),
                    low[n] = min(low[n], low[*it]);
        else if (in[*it])
            low[n] = min(low[n], low[*it]);
    }
    if (idx[n] == low[n]) {
        con.clear();
        int node;
        do {
            con.push_back(node = s.top());
            s.pop(), in[node] = 0;
        }
        while (node != n);
        scc.push_back(con);
    }
}



int main() {
    fi >> n >> m;

    rep(i,0,m) {
        fi >> x >> y;
        g[x].push_back(y);
    }

    rep(i,1,n+1) {
        if (!idx[i]) tarjan(i,g);
    }

    fo << scc.size() << endl;
    for (auto x:scc) {
        for (auto y:x) fo << y << ' ';
        fo << endl;
    }

    return 0;
}