Cod sursa(job #2928864)

Utilizator maria10Cioclov Maria maria10 Data 24 octombrie 2022 00:02:10
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, y, x, viz[100000], nrComp;
vector<vector<int>> lista, transp, comp;
vector<int> s, v;

void dfs1(int x){
    viz[x] = 1;
    for(auto i: lista[x])
        if(!viz[i]) dfs1(i);
    s.push_back(x);
}

void dfs2(int x){
    viz[x] = 0;
    comp[nrComp].push_back(x);
    for(auto i: transp[x])
        if(viz[i])
            dfs2(i);
}

int main(){
    fin>>n>>m;
    lista = transp = vector<vector<int>> (n);
    for(int i=0;i<m;i++) {
        fin>>x>>y;
        lista[x-1].push_back(y-1);
        transp[y-1].push_back(x-1);
    }

    for(int i=0;i<n;i++)
        if(!viz[i]) dfs1(i);

    while(!s.empty()){
        x = s.back();
        s.pop_back();
        if(viz[x]){
            comp.push_back(v);
            dfs2(x);
            nrComp++;
        }
    }

    fout<<nrComp<<endl;
    for(auto v: comp){
        for(auto i: v) fout<<i + 1<<" ";
        fout<<endl;
    }
}