Cod sursa(job #2927468)

Utilizator urluconceptualCiocan Alexandra-Diana urluconceptual Data 20 octombrie 2022 17:41:06
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

//4. elementele tare conexe intr-un graf orientat:
//proprietate a componentelor tare conexe in graful transpus: daca un nod este reachable din altul si in graful initial si in cel transpus
//(un ciclu ramane un ciclu si in graful transpus), atunci e clar ca ele se afla in aceeasi componenta conexa;
//astfel, facem 2 parcurgeri DF, una pe graful initial si una pe graful transpus;
//prima parcurgere este retinuta pe un stack in ordine inversa parcurgerii, pentru ca daca un nod e la final, asta inseamna ca el este
//extremitate initiala pentru un arc, iar parcurgerea pe graful transpus ne va asigura ca exista si extremitate finala, extremitatile finale
//devenind extremitati initiale pe graful traspus, deci locuri de pornire pentru DF;
//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, adjTrans;
vector<int> visited, temp;
stack<int> order;
//prima parcurgere DF, care memoreaza pe stack ordinea:
void DFS1(int node) {
    visited[node] = 1;
    for (int i = 0; i < adj[node].size(); i++)
        if (visited[adj[node][i]] == 0)
            DFS1(adj[node][i]);
    order.push(node);
}
//a doua parcurgere DF, care memoreaza componenta tare conexa curenta in vectorul "temp":
void DFS2(int node) {
    visited[node] = 1;
    temp.push_back(node);
    for (int i = 0; i < adjTrans[node].size(); i++)
        if (visited[adjTrans[node][i]] == 0)
            DFS2(adjTrans[node][i]);
}
//tranpunerea listei de adiacenta:
void transpose() {
    adjTrans.resize(n + 1);
    for (int i = 0; i < adj.size(); i++)
        for(int j=0; j<adj[i].size(); j++)
            adjTrans[adj[i][j]].push_back(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);
    //transpunerea:
    transpose();
    //a doua parcurgere:
    while (!order.empty()) {
        if (visited[order.top()] == 0) {
            DFS2(order.top());
            //memorarea ciclului din "temp" ca componenta tare conexa:
            scc.push_back(temp);
            temp.clear();
        }
        order.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;
}