Cod sursa(job #2945035)

Utilizator cberindeCodrin Berinde cberinde Data 23 noiembrie 2022 12:58:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int N, M, nrctc;
vector<int> adi[100001];
vector<int> adit[100001]; //graful transpus
stack<int> s;

vector<vector<int>> sol; //solutia problemei
bool viz[100001];

void citire() {
    cout << "u";
    int a, b;
    fin >> N >> M;
    for(int i = 1; i <= M; i++) {
        fin >> a >> b;
        adi[a].push_back(b);
        adit[b].push_back(a);
    }
}

void dfs(int nod) {
    for(int u : adi[nod]) {
        if(!viz[u]) {
            viz[u] = true;
            dfs(u);
        }
    }
    s.push(nod);
    cout << nod << " ";
}

void faza1() {
    //in faza 1 vom face cate un dfs din noduri arbitrare (toate acelea nevizitate)
    for(int start = 1; start <= N; start++) {
        if(!viz[start]) {
            viz[start] = true;
            dfs(start);
        }
    }
}

void dfs2(int nod) {
    for(int u : adit[nod]) {
        if(!viz[u]) {
            viz[u] = true;
            sol[nrctc - 1].push_back(u);
            dfs2(u);
        }
    }
}

void faza2() {
    //in faza 2 vom lua nodurile din stiva si facand dfs pe acelea vom gasi componentele tari conexe
    for(int i = 1; i <= N; i++) {
        viz[i] = false;
    }
    while(!s.empty()) {
        int start = s.top();
        s.pop();
        if(!viz[start]) {
            nrctc++;
            sol.push_back({});
            sol[nrctc - 1].push_back(start);
            viz[start] = true;
            dfs2(start);
        }

    }
}

void afisare() {
    fout << nrctc << "\n";
    for(int i = 0; i < nrctc; i++) {
        for(int u : sol[i]) {
            fout << u << " ";
        }
        fout << "\n";
    }
}

int main() {
    citire();
    faza1();
    faza2();
    afisare();
    return 0;
}