Cod sursa(job #971015)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 8 iulie 2013 11:44:36
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>
using namespace std;

const int MAX_N = 100002;

int N, M, Nr;
vector < int > v[MAX_N], w[MAX_N], comp[MAX_N], a;
bool m1[MAX_N], m2[MAX_N];

inline void DFS1(int x) {
    m1[x] = 1;
    for(size_t i = 0; i < v[x].size(); ++i)
        if(!m1[v[x][i]])
            DFS1(v[x][i]);
    a.push_back(x);
}

inline void DFS2(int x) {
    comp[Nr].push_back(x);
    m2[x] = 1;
    for(size_t i = 0; i < w[x].size(); ++i)
        if(!m2[w[x][i]])
            DFS2(w[x][i]);
}

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(!m1[i])
            DFS1(i);
    for(int i = a.size() - 1; i >= 0; --i)
        if(!m2[a[i]])
            ++Nr, DFS2(a[i]);

    g << Nr << '\n';
    for(int i = 1; i <= Nr; ++i) {
        for(size_t j = 0; j < comp[i].size(); ++j)
            g << comp[i][j] << " ";
        g << '\n';
    }

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

    return 0;
}