Cod sursa(job #2927395)

Utilizator urluconceptualCiocan Alexandra-Diana urluconceptual Data 20 octombrie 2022 12:24:23
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.64 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

//4. elementele tare conexe intr-un graf orientat:
//elementele tare conexe sunt cele in care se formeaza cicluri, deci trebuie sa cautam ciclurile, adica seturile de noduri in care
//putem sa ne plimbam prin noduri => fiecare nod este si extremitate finala si extremitate initiala pentru cate un arc;
//intr-o parcurgere DF, un nod este extremitate finala pentru un arc care incepe intr-un nod din stanga lui, deci o sa pargurg DF
//graful memorand cu ajutorul unei stive ordinea parcurgerii;
//voi folosi stackul pentru a lua cate o extremitate finala si a verifica daca ea este si extremitate initiala, parcurgand DF;
//parcurgerile noi sunt chiar componentele tare conexe;
//complexitate: O(n+m) = 2 parcurgeri DF, unde n=numarul de varfuri, m=numarul de muchii

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

int n, m;
vector<vector<int>> adj, scc;
vector<int> visited, temp;
stack<int> preorder;
//prima parcurgere DF, care memoreaza pe stack ordinea:
void DFS1(int node) {
    visited[node] = 1;
    preorder.push(node);
    for (int i = 0; i < adj[node].size(); i++)
        if (visited[node] == 0)
            DFS1(node);
}
//a doua parcurgere DF, care memoreaza ciclul curent in vectorul "temp":
void DFS2(int node) {
    visited[node] = 1;
    temp.push_back(node);
    for (int i = 0; i < adj[node].size(); i++)
        if (visited[adj[node][i]] == 0)
            DFS2(adj[node][i]);
}
//functia care cauta componentele tare conexe:
void SCC() {
    //prima parcurgere:
    for (int i = 1; i <= n; i++)
        if (visited[i] == 0)
            DFS1(i);
    visited.clear();
    visited.resize(n + 1, 0);
    //a doua parcurgere:
    while (!preorder.empty()) {
        if (visited[preorder.top()] == 0) {
            DFS2(preorder.top());
            //memorarea ciclului din "temp" ca componenta tare conexa:
            scc.push_back(temp);
            temp.clear();
        }
        preorder.pop();
    }
}

int main()
{
    fin >> n >> m;
    adj.resize(n+1);
    visited.resize(n+1, 0);
    //stocarea datelor de intrare intr-o lista de adiacenta:
    for (int i = 0; i < m; i++) {
        int node1, node2;
        fin >> node1 >> node2;
        adj[node1].push_back(node2);
    }
    //apelarea functiei care cauta componentele tare conexe:
    SCC();
    //afisarea rezultatului:
    fout << scc.size() << "\n";
    for (int i = 0; i < scc.size(); i++) {
        for (int j = 0; j < scc[i].size(); j++)
            fout << scc[i][j] << " ";
        fout << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}