Cod sursa(job #2927821)

Utilizator TindecheTindeche Alexandru Tindeche Data 21 octombrie 2022 16:34:44
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.7 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int n, m;
// Facem o clasa nod pentru a retine informatiile despre noduri
// Aici retinem lista de vecini pentru fiecare nod si lista de vecini daca muchiile ar fi inversate
class node
{
    public:
    vector <int> adicente;
    vector <int> rev_adiacente;
};
// Lista de noduri
vector <node> noduri;
int numar_componente = 0;
// Vector de vizitati
int vizitat[100000];
// Facem un stack pentru a retine nodurile in care ajungem si am terminat de vizitat toti vecinii
stack <int> s;
vector <vector <int>> componente;

void dfs1(int start)
{
    // Marcam nodul ca vizitat
    vizitat[start] = 1;
    // Parcurgem lista de vecini
    for (int i = 0; i < noduri[start].adicente.size(); i++)
    {
        // Daca nu a fost vizitat, il vizitam
        if (vizitat[noduri[start].adicente[i]] == 0)
        {
            dfs1(noduri[start].adicente[i]);
        }
    }
    // Adaugam nodul in stack dupa ce am terminat de vizitat toti vecinii lui
    s.push(start);
}

void dfs2(int start)
{
    // Adaugam in componenta tare conexa
    componente[numar_componente].push_back(start);
    // Marcam nodul ca vizitat
    vizitat[start] = 1;
    // Parcurgem lista de vecini
    for (int i = 0; i < noduri[start].rev_adiacente.size(); i++)
    {
        // Daca nu a fost vizitat, il vizitam
        if (vizitat[noduri[start].rev_adiacente[i]] == 0)
        {
            dfs2(noduri[start].rev_adiacente[i]);
        }
    }
}

void kosaraju()
{
    // Facem dfs pentru
    for(int i = 0; i < n; i++)
        if(!vizitat[i])
            dfs1(i);

    // Resetam vectorul de vizitati
    for(int i = 0; i < n; i++)
        vizitat[i] = 0;

    // Parcurgem stack-ul si facem dfs pentru fiecare nod din stack
    // cu muchiile inversate

    while (!s.empty())
    {
        int nod = s.top();
        s.pop();
        // Daca nu e vizitat inseamna ca e o componenta tare conexa noua
        if (!vizitat[nod])
        {
            dfs2(nod);
            numar_componente++;
        }
    }

}

int main()
{
    fin >> n >> m;
    noduri.resize(n + 1);
    componente.resize(n + 1);
    for(int i = 0; i < m; i++)
    {
        int x, y;
        fin >> x >> y;
        // Adaugam muchia in lista de vecini a nodului x si la lista inversata
        noduri[x].adicente.push_back(y);
        noduri[y].rev_adiacente.push_back(x);
    }

    // Aplicam algoritmul lui Kosaraju
    kosaraju();
    fout << numar_componente << '\n';
    for(int i = 0; i < numar_componente; i++)
    {
        for (int j = 0; j < componente[i].size(); j++)
            fout << componente[i][j] << " ";
        fout << '\n';
    }
    return 0;
}