Cod sursa(job #2263100)

Utilizator EclipseTepes Alexandru Eclipse Data 18 octombrie 2018 10:17:40
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.76 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, idx;

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];

char sir[20];

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 GetInts(int &a, int &b) {
    int t = 0;
    idx = 0;
    fin.getline(sir, 20);
    while (isdigit(sir[idx])) {
        t *= 10;
        t += sir[idx] - '0';
        idx++;
    }
    a = t;
    idx++;
    t = 0;
    while (isdigit(sir[idx])) {
        t *= 10;
        t += sir[idx] - '0';
        idx++;
    }
    b = t;

}

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;

    GetInts(n, m);
    //fin >> n >> m;

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

        GetInts(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;

}