Cod sursa(job #1963443)

Utilizator misu007Pogonaru Mihai misu007 Data 12 aprilie 2017 15:41:01
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.57 kb
#include <iostream>
#include <cstdio>
#include <list>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

typedef pair<int, int> Pair;

#define G 0 //graf initial
#define T 1 //graf transpus

int n, m, nrsol;
vector<int> culoare;
vector<list<int>> graf[2];
vector<int> sortareVector;
vector<vector<int>> solutiones;
stack<int> stiva;

void read() {
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);

    int n1, n2;
    cin >> n >> m;
    culoare.resize(n);
    graf[G].resize(n);
    graf[T].resize(n);
    sortareVector.resize(n);
    for(int i = 0; i < m; ++i) {
        scanf("%d%d", &n1, &n2);
        graf[G][n1 - 1].push_back(n2 - 1); //graf
        graf[T][n2 - 1].push_back(n1 - 1); //graf transpus
    }
}

void DFS(int nod, bool TR);

void Kosaraju() {
    bool continua = true;
    while (continua) {
        int nod = 0;
        while (nod < n && culoare[nod]) {
            ++nod;
        }

        if (nod == n) {
            continua = false;
            continue;
        }

        DFS(nod, G);
    }

    culoare = vector<int>(n);
    while(!stiva.empty()) {
        int nod = stiva.top();
        stiva.pop();
        if (!culoare[nod]) {
            solutiones.push_back(vector<int>());
            DFS(nod, T);
            nrsol++;
        }
    }
}

void DFS(int nod, bool TR) {
    culoare[nod] = 1;
    for (auto vecin : graf[TR][nod]) {
        if (!culoare[vecin]) {
            DFS(vecin, TR);
        }
    }
    culoare[nod] = 2;
    if (TR == G) {
        stiva.push(nod);
    } else {
        solutiones[nrsol].push_back(nod + 1);
    }
}

void write() {
    printf("%d\n", nrsol);
    for(int i = 0; i < nrsol; ++i) {
        for (auto x : solutiones[i]) {
            printf("%d ", x);
        }
        printf("\n");
    }
}

int main()
{
    read();
    Kosaraju();
    write();
//    for (int nod = 0; nod < n; ++nod) {
//        for (auto vecin : noduri[nod]) {
//            cout << vecin << " ";
//        }
//        cout << endl;
//    }
//
//    for (int nod = 0; nod < n; ++nod) {
//        cout << "nod: " << nod + 1 << " culoare: "
//        << culoare[nod] << " timpi: " << timpi[nod].first
//        << " " << timpi[nod].second << endl;
//    }
//    int nod = 0;
//    while (!stiva.empty()) {
//        sortareVector[nod++] = stiva.top();
//        stiva.pop();
//    }
//    cout << endl << "Sortare: ";
//    for (int nod = 0; nod < n; ++nod) {
//        cout << sortareVector[nod] + 1 <<" ";
//    }
    return 0;
}