Cod sursa(job #2250518)

Utilizator pinteastefanPintea Teodor Stefan pinteastefan Data 30 septembrie 2018 14:29:39
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;
vector <int> graff[100001];
vector <int> reverseGraff[100001];
vector <int> values(100001);
vector <int> CTC[100001];
int vizitate[100001];
int ctc[100001];
int numberOfCTC = 0;

void dfsGraff(int nod) {
    vizitate[nod] = 1;
    for (auto x : graff[nod]) {
        if (vizitate[x] == 0) {
            dfsGraff(x);
        }
    }
    values.push_back(nod);
}
void dfsRevGraff(int nod, int pozitie){
    CTC[pozitie].push_back(nod);
    vizitate[nod] = 0;
    for (auto x : reverseGraff[nod]){
        if(vizitate[x]){
            dfsRevGraff(x, pozitie);
        }
    }
}

int main() {
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    int n, m;
    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        f >> x >> y;
        graff[x].push_back(y);
        reverseGraff[y].push_back(x);
    }
    for (int i = 1; i<=n; i++){
        if(vizitate[i] == 0) {
            dfsGraff(i);
        }
    }

    reverse(values.begin(), values.end());

    for (auto x : values){
        if (vizitate[x]){
            numberOfCTC ++;
            dfsRevGraff(x, numberOfCTC);
        }
    }

    g << numberOfCTC << "\n";
    for (int i = 1; i <= numberOfCTC; i++){
        for( auto j : CTC[i]){
            g << j << " ";
        }
        g << "\n";
    }
    return 0;
}