Cod sursa(job #3372587)

Utilizator CiulinAndreeaCiulin Andreea Iuliana CiulinAndreea Data 4 noiembrie 2026 12:42:23
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
using namespace std;

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

vector<int> graf[100001];
vector<int> grafInv[100001];
bool vizitat1[100001];
bool vizitat2[100001];
vector<int> ordine;
vector<int> comp;
vector<vector<int>> componente;

void DFS1(int nod) {
    vizitat1[nod]=true;

    for (int vecin : graf[nod]) {
        if (!vizitat1[vecin])
            DFS1(vecin);
    }
    ordine.push_back(nod);
}
void DFS2(int nod) {
    vizitat2[nod]=true;
    comp.push_back(nod);

    for (int vecin : grafInv[nod]) {
        if (!vizitat2[vecin])
            DFS2(vecin);
    }
}

int main() {
    int N, M, x, y;
    fin>>N>>M;
    for (int i=1; i<=M; i++) {
        fin>>x>>y;
        graf[x].push_back(y);
        grafInv[y].push_back(x);
    }
    for (int i=1; i<=N; i++) {
        if (!vizitat1[i])
            DFS1(i);
    }
    for (int i=ordine.size()-1; i>=0; i--) {
        if (!vizitat2[ordine[i]]) {
            comp.clear();
            DFS2(ordine[i]);
            componente.push_back(comp);
        }
    }
    fout<<componente.size()<<'\n';
    for (auto comp : componente) {
        for (int nod : comp)
            fout<<nod<<" ";
        fout<<'\n';
    }
}