Cod sursa(job #1665154)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 26 martie 2016 17:04:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>
using namespace std;

const int N = 100100;

int n, m;
vector<int> g[N], gt[N];
bool vis[N];
int cind[N];
vector<int> procList;
vector<int> scc[N];

void firstPass(const int &cur) {
    vis[cur] = true;
    for(const auto nxt : g[cur]) {
        if(vis[nxt] == false) {
            firstPass(nxt);
        }
    }
    procList.push_back(cur);
}

void secondPass(const int &cur, const int &component) {
    cind[cur] = component;
    scc[component].push_back(cur);
    for(const auto nxt : gt[cur]) {
        if(cind[nxt] == 0) {
            secondPass(nxt, component);
        }
    }
}

int main() {
    ifstream in("ctc.in");
    ofstream out("ctc.out");

    int i, x, y, ind;

    in >> n >> m;
    for(i = 1; i <= m; i++) {
        in >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }

    ind = 0;
    for(i = 1; i <= n; i++) {
        if(vis[i] == false) {
            firstPass(i);
        }
    }
    for(i = n - 1; i >= 0; i--) {
        if(cind[procList[i]] == 0) {
            ++ind;
            secondPass(procList[i], ind);
        }
    }

    out << ind << '\n';
    for(i = 1; i <= ind; i++) {
        for(const auto j : scc[i]) {
            out << j << ' ';
        }
        out << '\n';
    }

    return 0;
}