Cod sursa(job #3372762)

Utilizator licadariaLica Daria licadaria Data 4 noiembrie 2026 21:46:35
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include<vector>
#include<fstream>
#include <stack>
#include <utility>
using namespace std;

vector<vector<int>> graf;
vector<vector<int>> graf_inv;
int nr_cnx=0;
vector<int> vizitat;
stack <int> sortat;
vector<pair<int, int>> ordine;

void Dfs1(int curent){
    vizitat[curent] = 1;
    for (int t = 0; t<graf[curent].size(); t++) {
        int vecin = graf[curent][t];
        if (vizitat[vecin]==0) Dfs1(vecin);
    }
    sortat.push(curent);}

void Dfs2(int curent){
    vizitat[curent] = nr_cnx;
    ordine.push_back({curent, nr_cnx});
    for (int t = 0; t<graf_inv[curent].size(); t++) {
        int vecin = graf_inv[curent][t];
        if (vizitat[vecin]==0) Dfs2(vecin);
    }
}


int main() {
    ifstream fin("ctc.in");
    int N, M, x,y;
    fin>>N>>M;
    graf.resize(N+1);
    graf_inv.resize(N+1);

    for (int i =0; i<M; i++) {
        fin>>x>>y;
        graf[x].push_back(y);
        graf_inv[y].push_back(x);
    }
    fin.close();
    vizitat.resize(N+1);
    for (int i = 0; i<=N; i++){vizitat[i] = 0;}

    for (int i=1; i<=N; i++) {
        if (vizitat[i]==0) Dfs1(i);
    }

    for (int i = 0; i<=N; i++){vizitat[i] = 0;}

    while (!sortat.empty()) {
        int curent = sortat.top();
        sortat.pop();
        if (vizitat[curent]==0) {
            nr_cnx++;
            Dfs2(curent);
        }
    }

    ofstream fout("ctc.out");
    fout<<nr_cnx;
    int ult = 0;
    for (int i =0; i<ordine.size(); i++) {
        if (ordine[i].second != ult){fout<<"\n"; ult = ordine[i].second;}
        fout<<ordine[i].first<< "  ";
    }
    fout.close();
    return 0;
}