Cod sursa(job #1165290)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 2 aprilie 2014 16:44:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>
using namespace std;

const int MAX_N = 100002;

int N, M, nrSCC;
vector < int > v[MAX_N], w[MAX_N], SCC[MAX_N], a;
bool m[MAX_N];

void DFS1(int x) {
    m[x] = 1;

    for(int i = 0; i <  (int) v[x].size(); ++i) {
        int y = v[x][i];
        if(!m[y])
            DFS1(y);
    }

    a.push_back(x);
}

void DFS2(int x) {
    m[x] = 1;
    SCC[nrSCC].push_back(x);

    for(int i = 0; i < (int) w[x].size(); ++i) {
        int y = w[x][i];

        if(!m[y])
            DFS2(y);
    }
}

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

    f >> N >> M;
    for(int i = 1, x, y; i <= M; ++i) {
        f >> x >> y;
        v[x].push_back(y);
        w[y].push_back(x);
    }

    for(int i = 1; i <= N; ++i)
        if(!m[i])
            DFS1(i);

    for(int i = 1; i <= N; ++i)
        m[i] = 0;
    for(int i = a.size() - 1; i >= 0; --i)
        if(!m[a[i]]) {
            ++nrSCC;
            DFS2(a[i]);
        }

    g << nrSCC << "\n";
    for(int i = 1; i <= nrSCC; ++i) {
        for(int j = 0; j < (int) SCC[i].size(); ++j)
            g << SCC[i][j] << " ";
        g << "\n";
    }

    f.close();
    g.close();

    return 0;
}