Cod sursa(job #2159509)

Utilizator OpportunityVlad Negura Opportunity Data 10 martie 2018 23:25:07
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 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("ctc.in");
ofstream fo("ctc.out");

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

void tarjan(int v) {
    idx[v] = low[v] = idxc;
    idxc++;
    s.push(v);
    in[v] = 1;

    for (auto &u:g[v]) {
        if (idx[u] == 0){
            tarjan(u);
            low[v] = min(low[v], low[u]);
        } else if (in[u]) {
            low[v] = min(low[v], idx[u]);
        }
    }

    vector<int> comp;
    if (low[v] == idx[v]) {
        int u;
        do {
            u = s.top();
            in[u] = 0;
            s.pop();
            comp.push_back(u);
        } while(u != v);
        scc.push_back(comp);
    }
}


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);
    }

    fo << scc.size() << endl;
    rep(i,0,scc.size()) {
        rep(j,0,scc[i].size()) fo << scc[i][j] << ' ';
        fo << endl;
    }

    return 0;
}