Cod sursa(job #2798664)

Utilizator FraNNNkieFrancesco-Gregorio Petrovici FraNNNkie Data 11 noiembrie 2021 17:52:24
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100005


using namespace std;

vector <int> la[NMAX], lat[NMAX], ctc[NMAX];
stack <int> s;
int nrc = 0;
int n, m;
int viz[NMAX];

void dfs(int start){
    viz[start] = 1;
    int nrv = la[start].size();
    for(int i = 0; i < nrv; ++i){
        if(!viz[la[start][i]]){
            dfs(la[start][i]);
        }
    }
    s.push(start);
}
void dfsTrans (int start){
    viz[start] = 2;
    ctc[nrc].push_back(start);
    int nrv = lat[start].size();
    for(int i = 0; i < nrv; ++i){
        if(viz[lat[start][i]] == 1){
            dfsTrans(lat[start][i]);
        }
    }
}
void solve(){
    for(int i = 1; i <= n; ++i){
        if(!viz[i]){
            dfs(i);
        }
    }
    while(!s.empty()){
        int k = s.top();
        if(viz[k] == 1){
            nrc++;
            dfsTrans(k);
        }
        s.pop();
    }
}
int main()
{
    ifstream f("ctc.in");
    f >> n >> m;
    for(int i = 0; i <= m; ++i){
        int a, b;
        f >> a >> b;
        la[a].push_back(b);
        lat[b].push_back(a);
    }
    f.close();
    ofstream g("ctc.out");
    solve();

    g << nrc << "\n";
    for(int i = 1; i <= nrc; ++i){
        int sz = ctc[i].size();
        for(int j = 0; j < sz; ++j){
            g << ctc[i][j] << " ";
        }
        g << "\n";
    }
    return 0;
}