Cod sursa(job #2159527)

Utilizator OpportunityVlad Negura Opportunity Data 10 martie 2018 23:40:42
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 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,idxc;
vector<int> idx, in, low, g[100001];
vector<vector<int>> scc;
stack<int> s;

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

    for (auto &u:g[v]) {
        if (idx[u] == -1){
            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;
    in.resize(n);
    low.resize(n);
    idx.resize(n);
    in.assign(n,0);
    idx.assign(n,-1);

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

    rep(i,0,n) {
        if (idx[i] == -1) tarjan(i);
    }

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

    return 0;
}