Cod sursa(job #2262976)

Utilizator EclipseTepes Alexandru Eclipse Data 17 octombrie 2018 23:05:01
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 kb
#include <iostream>
#include <fstream>
#include <vector>
#define dMAX 100000

using namespace std;

int n, m, lvl, nrTare;
int x, y;
vector<int> graf[dMAX + 2];
vector<int> grafT[dMAX + 2];

int plusminus[dMAX + 2];

bool viz[dMAX + 2], vizpm[dMAX + 2];

vector<pair<int, int> > nivel;
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);
    }
    nivel.push_back({k, ++lvl});
    viz[k] = false;
}

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]++;
    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);
        }
    }
    //vizpm[k] = false;
}

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);
    }

    DFS_N(1);

    for (i = 1; i <= n; i++) {
        if (!viz[i]) {
            viz[i] = true;
            nrTare++;
            for (j = 1; j <= n; j++) {
                plusminus[j] = 0;
            }
            DFS_P(i);
            for (j = 1; j <= n; j++) vizpm[j] = false;
            DFS_M(i);
            for (j = 1; j <= n; j++) vizpm[j] = false;
            for (j = 1; j <= n; j++) {
                //cout << plusminus[j] << ' ';
                if (plusminus[j] == 2) {
                    viz[j] = true;
                    componente[nrTare].push_back(j);
                    //cout << j << ' ';
                }
            }
            //cout << '\n';
        }
    }
    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;
}