Cod sursa(job #1655011)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 17 martie 2016 17:45:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>
using namespace std;

vector <int> adia[100010];
vector <int> adiaback[100010];
vector <int> sortop;
vector <int> componente[100010];
int c = 0;
bool viz[100010];
bool vizback[100010];
int n, m;

void bkt(int nod);
void bktback(int nod, int nr);

int main()
{
    ifstream in("ctc.in");
    in >> n >> m;
    int a, b;
    for (int i = 0; i < m; i++) {
        in >> a >> b;
        adia[a].push_back(b);
        adiaback[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        if ( !viz[i] ) {
            bkt(i);
        }
    } /// sortare topologica

    for (int i = sortop.size() - 1; i >= 0; i--) {
        if ( vizback[sortop[i]] )
            continue;
        bktback(sortop[i], c);
        c++;
    }
    ofstream out("ctc.out");
    out << c;
    for (int i = 0; i < c; i++) {
        out << '\n';
        for (auto j : componente[i]) {
            out << j << ' ';
        }
    }
    return 0;
}

void bktback(int nod, int nr) {
    vizback[nod] = 1;
    componente[nr].push_back(nod);
    for (auto i : adiaback[nod]) {
        if ( !vizback[i] ) {
            bktback(i, nr);
        }
    }
}

void bkt(int nod) {
    viz[nod] = 1;
    for (auto i : adia[nod]) {
        if ( !viz[i] )
            bkt(i);
    }
    sortop.push_back(nod);
}