Cod sursa(job #2927588)

Utilizator Cosmin3105Cosmin Colceru Cosmin3105 Data 20 octombrie 2022 21:42:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 100005;
vector<int> la[NMAX], laT[NMAX], rezultat[NMAX];
int n, m, nr;
int viz[NMAX];
stack <int> stiva;

void dfs(int nod) {
    viz[nod] = 1;
    for(int i = 0; i < la[nod].size(); i++) {
        int vecin = la[nod][i];
        
        if(!viz[vecin])
            dfs(vecin);
    }
    stiva.push(nod);
}

void dfsT(int nod) {
    viz[nod] = 2;
    rezultat[nr].push_back(nod);
    
    for(int i = 0; i < laT[nod].size(); i++) {
        int vecin = laT[nod][i];
        
        if(viz[vecin] == 1)
            dfsT(vecin);
    }
}

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

    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs(i);

    while (!stiva.empty()) {
        int nod = stiva.top();
        if (viz[nod] == 1) {
            nr++;
            dfsT(nod);
        }
        stiva.pop();
    }
    
    fout << nr <<  endl;
    for(int i = 1; i <= nr; i++) {
        for(int j = 0; j < rezultat[i].size(); j++)
            fout << rezultat[i][j] <<" ";
        fout << endl;
    }

    return 0;
}