Cod sursa(job #2929517)

Utilizator Emma19Tiu Ema Emma19 Data 25 octombrie 2022 23:38:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.64 kb
/**
DESCRIEREA REZOLVARII: complexitate O(N + M)

Am utilizat ALGORITMUL LUI TARJAN care presupune:
 1.Pt fiecare nod nevizitat pornim o parcurgere dfs
 2.La vizitarea unui nod acesta este adaugat pe stiva si primeste un id
 3.Pentru nodul curent vizitam totate nodurile adiacente
 4.Deoarece oferim id-urile in ordine crescatoare, primul nod vizitat dintr-o componenta conexa ca vi nodul cu id-ul cel mai mic
  astfel, cand ajungem cu parcurgerea la un nod cu un id mai mic, stim ca apartin aceleiasi componente conexe
 5.dupa acest procedeu, daca id-ul curent este egal cu low-ul, nodul curent este un nod de "inceput" pentru componenta conexa a lui
  asftel scoatem de pe stack nodurile pana ajungem la cel curent, iar acestea vor fi parte a componentei conexe curente

**/


#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>


using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

stack <int> stiva;
vector <int> adiacenta[100001];
vector <vector <int>> rez;
int id[100001],verif[100001], low[100001], idcurent=1,componente=0;
//verif ne spune daca un nod se afla sau nu pe stiva
//id ne spune daca un nod a fost sau nu vizitat, iar daca da, ce Id a primit



void dfs(int curent) {
    id[curent] = idcurent;
    low[curent] = idcurent;
    idcurent++;
    stiva.push(curent);
    verif[curent] = 1;

    for (int i=0;i < adiacenta[curent].size();i++) {
        if (id[ adiacenta[curent][i]] == 0) {
            dfs(adiacenta[curent][i]);
            low[curent] = min(low[curent], low[adiacenta[curent][i]]);
        }
        else if (verif[adiacenta[curent][i]]) {
            low[curent] = min(low[curent], id[adiacenta[curent][i]]);
        }
    }
    if (id[curent] == low[curent]) {
        vector <int> comp;
        int node;

        node = stiva.top();
        stiva.pop();
        verif[node] = 0;
        comp.push_back(node);

        while (curent != node) {
            node = stiva.top();
            stiva.pop();
            verif[node] = 0;
            comp.push_back(node);
        } ;
        rez.push_back(comp);
        componente++;
    }
}


int main() {

    int n,m,x,y;
    f>>n>>m;
    for (int i = 1; i <= m; i++)
        {
        f>>x>>y;
        adiacenta[x].push_back(y);
       }

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

    g<< componente <<'\n';
    for (int i = 0; i < rez.size(); i++) {
        for (int j = 0; j < rez[i].size(); j++) {
            g<< rez[i][j] << " ";
        }
        g<<'\n';
    }
    return 0;
}