Cod sursa(job #2263097)

Utilizator EclipseTepes Alexandru Eclipse Data 18 octombrie 2018 10:13:54
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.39 kb
#include <iostream>

#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#define dMAX 100000



using namespace std;



int n, m, lvl, nrTare;

int x, y;

vector<int> graf[dMAX + 2];

vector<int> grafT[dMAX + 2];

pair<int, int> nivel[dMAX + 2];
int plusminus[dMAX + 2];
bool viz[dMAX + 2], vizpm[dMAX + 2];
vector<int> componente[dMAX + 2];

ifstream fin("ctc.in");
ofstream fout("ctc.out");

void DFS_N(int k) {

    viz[k] = true;

    for (int i = 0; i < graf[k].size(); i++) {

        int newV = graf[k][i];

        if (!viz[newV]) {
            DFS_N(newV);
            //lvl++;
        }

    }

    nivel[k] = {k, ++lvl};
}



void DFS_P(int k) {

    plusminus[k]++;

    vizpm[k] = true;

    for (int i = 0; i < graf[k].size(); i++) {

        int newV = graf[k][i];

        if (!vizpm[newV] && !viz[newV]) {

            DFS_P(newV);

        }

    }

    //vizpm[k] = false;

}



void DFS_M(int k) {

    plusminus[k]++;
    if (plusminus[k] == 2) {
        viz[k] = true;
        componente[nrTare].push_back(k);
    }

    vizpm[k] = true;

    for (int i = 0; i < grafT[k].size(); i++) {

        int newV = grafT[k][i];

        if (!vizpm[newV] && !viz[newV]) {

            DFS_M(newV);

        }

    }

}

bool Compare(pair<int, int> e1, pair<int, int> e2) {
    return e1.second < e2.second;
}

int main()

{

    int i, j;

    fin >> n >> m;

    for (i = 1; i <= m; i++) {

        fin >> x >> y;

        graf[x].push_back(y);

        grafT[y].push_back(x);

    }
    for (i = 1; i <= n; i++) {
        if (!viz[i]) {
            DFS_N(i);
        }
    }
    memset(viz, false, sizeof(viz));
    sort(nivel + 1, nivel + 1 + n, Compare);
    for (i = 1; i <= n; i++) {
        int pVerif = nivel[i].first;
        if (!viz[pVerif]) {
            viz[pVerif] = true;
            nrTare++;
            memset(vizpm, false, sizeof(vizpm));
            memset(plusminus, false, sizeof(plusminus));
            DFS_P(pVerif);
            memset(vizpm, false, sizeof(vizpm));
            DFS_M(pVerif);
        }

    }

    fout << nrTare << '\n';

    for (i = 1; i <= nrTare; i++) {

        for (j = 0; j < componente[i].size(); j++) {

            fout << componente[i][j] << ' ';

        }

        fout << '\n';
    }
    return 0;

}