Cod sursa(job #2675899)

Utilizator LittleGreenMenMihai A LittleGreenMen Data 22 noiembrie 2020 19:47:19
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

#define MAX_N 100005

using namespace std;

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

int N, M;
stack<int> S;
vector<int> adiac[MAX_N];
vector<int> inv_adiac[MAX_N];
vector<int> ctc[MAX_N];
int nr_ctc;
char vizitat[MAX_N];

void DFSP(vector<int> m[], int nod)
{
    int i;

    vizitat[nod] = 1;

    for(i = 0; i < m[nod].size(); i++)
        if(vizitat[m[nod][i]] != 1)
            DFSP(m, m[nod][i]);

    S.push(nod);
}

void DFSS(vector<int> m[], int nod)
{
    int i;

    vizitat[nod] = 2;
    ctc[nr_ctc].push_back(nod);

    for(i = 0; i < m[nod].size(); i++)
        if(vizitat[m[nod][i]] != 2)
            DFSS(m, m[nod][i]);
}

int main()
{
    int x, y, i, j;

    in >> N >> M;
    for(i = 0; i < M; i++) {
        in >> x >> y;

        adiac[x].push_back(y);
        inv_adiac[y].push_back(x);
    }

    for(i = 1; i <= N; i++)
        if(!vizitat[i])
            DFSP(inv_adiac, i);

    while(!S.empty()) {
        if(vizitat[S.top()] == 1) {
            DFSS(adiac, S.top());
            nr_ctc++;
        }
        S.pop();
    }

    out << nr_ctc << '\n';
    for(i = 0; i < nr_ctc; i++) {
        for(j = 0; j < ctc[i].size(); j++)
            out << ctc[i][j] << ' ';
        out << '\n';
    }

    in.close();
    out.close();

    return 0;
}