Cod sursa(job #2926152)

Utilizator IRadu1529Radu Ionescu IRadu1529 Data 17 octombrie 2022 09:29:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <fstream>
using namespace std;

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

const int nmax = 1e5 + 1;

vector <int> g[nmax], gt[nmax], compConexe[nmax];
stack <int> st;
int viz[nmax], nrComp;

void DFS1(int nod)
{
    viz[nod] = 1;
    for (int i = 0; i < g[nod].size(); ++i) {
        int aux = g[nod][i];
        if (viz[aux] == 0) {
            DFS1(aux);
        }
    }
    st.push(nod);
}

void DFS2(int nod)
{
    viz[nod] = 2;
    compConexe[nrComp].push_back(nod);
    for (int i = 0; i < gt[nod].size(); ++i) {
        int aux = gt[nod][i];
        if (viz[aux] == 1) {
            DFS2(aux);
        }
    }
}

int main()
{


    int n, m;
    int x, y;
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        fin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }

    for (int i = 1; i <= n; ++i) {
        if (viz[i] == 0) {
            DFS1(i);
        }
    }
    while (!st.empty()) {
        int nod = st.top();
        if (viz[nod] == 1) {
            ++nrComp;
            DFS2(nod);
        }
        st.pop();
    }
    fout << nrComp << "\n";
    for (int i = 1; i <= nrComp; ++i) {
        for (int aux : compConexe[i])
            fout << aux << " ";
        fout << "\n";
    }
    return 0;
}