Cod sursa(job #2263094)

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

#include <fstream>

#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);
        }
    }
    for (i = 1; i <= n; i++) {
        viz[i] = false;
    }
    sort(nivel + 1, nivel + 1 + n, Compare);
    for (i = 1; i <= n; i++) {
        int pVerif = nivel[i].first;
        if (!viz[pVerif]) {
            //cout << pVerif << '\n';
            viz[pVerif] = true;

            nrTare++;

            for (j = 1; j <= n; j++) {

                plusminus[j] = 0;

            }

            DFS_P(pVerif);
            for (j = 1; j <= n; j++) vizpm[j] = false;
            DFS_M(pVerif);
            for (j = 1; j <= n; j++) vizpm[j] = false;
            /*for (j = 1; j <= n; j++) {
                if (plusminus[j] == 2) {
                    viz[j] = true;
                    componente[nrTare].push_back(j);
                }
            }*/

        }

    }

    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;

}