Cod sursa(job #2968063)

Utilizator petru.theodor07Petru Cristea petru.theodor07 Data 20 ianuarie 2023 17:43:14
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>

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

vector<int> graf[100100], graf_transpus[100100], ctc[100100];
int n, m, cc=0, viz[100100];
vector<int> ord;

void dfs(int nod){
    viz[nod] = true;
    for(int i=0; i<(int)graf[nod].size(); i++){
        if(viz[graf[nod][i]] == false)
            dfs(graf[nod][i]);
    }
    ord.push_back(nod);

}


void dfs__cc(int nod){
    viz[nod] = true;
    ctc[cc].push_back(nod);
    for(int i=0; i<(int)graf_transpus[nod].size(); i++){
        if(viz[graf_transpus[nod][i]] == false)
            dfs__cc(graf_transpus[nod][i]);
    }
}

int main(){
    fin>>n>>m;
    for(int i=0; i<m; i++){
        int x, y;
        fin>>x>>y;
        graf[x].push_back(y);
        graf_transpus[y].push_back(x);
    }

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

    for(int i=1; i<=n; i++)
        viz[i] = false;

    for(int i=ord.size()-1; i>=0; i--){
        if(viz[ord[i]] == false){
            dfs__cc(ord[i]);
            cc++;
        }
    }

    fout<<cc<<endl;

    for(int i=0; i<cc; i++){
        for(int j=0; j<(int)ctc[i].size(); j++)
            fout<<ctc[i][j]<< ' ' ;
        fout<<endl;
    }
}