Cod sursa(job #492267)

Utilizator MariusMarius Stroe Marius Data 13 octombrie 2010 23:02:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

const char iname[] = "ctc.in";
const char oname[] = "ctc.out";

const int MAX_N = 100005;

vector <int> Go[MAX_N], Gi[MAX_N], where[MAX_N], used, discovered;

void DFP(int n, vector <int> *G) {
    vector <int>::iterator it;

    used[n] = true;
    for (it = G[n].begin(); it != G[n].end(); ++ it) if (!used[*it])
        DFP(*it, G);
    discovered.push_back(n);
}

void DFM(int n, vector <int>* G, int which) {
    vector <int>::iterator it;

    used[n] = true;
    where[which].push_back(n);
    for (it = G[n].begin(); it != G[n].end(); ++ it) if (!used[*it])
        DFM(*it, G, which);
}

int main(void) {
    int nodes, edges, x, y;

    ifstream in(iname);
    in >> nodes >> edges;
    while (edges --) {
        in >> x >> y;
        Go[x - 1].push_back(y - 1);
        Gi[y - 1].push_back(x - 1);
    }
    in.close();

    used.resize(nodes);
    used.assign(used.size(), false);
    for (int i = 0; i < (int) used.size(); ++ i) if (!used[i])
        DFP(i, Go);

    used.assign(used.size(), false);
    int count = 0;
    for (; discovered.size(); discovered.pop_back()) {
        if (!used[discovered.back()])
            DFM(discovered.back(), Gi, count ++);
    }

    ofstream out(oname);
    out << count << '\n';
    for (int i = 0; i < (int) count; ++ i) {
        for (int j = 0; j < (int) where[i].size(); ++ j)
            out << (where[i][j] + 1) << " ";
        out << '\n';
    }
    out.close();

    return 0;
}