Cod sursa(job #2925691)

Utilizator Rincu_StefaniaRincu Stefania Rincu_Stefania Data 15 octombrie 2022 21:27:48
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.14 kb
#include <iostream>
#include <fstream>
#include <map>
#include <list>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;

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

map<int, list<int>> l;
vector<vector<int>> c;
vector<int> vect;
stack<int> s;

///ind -> memoreaza indicele nodurilor in ordinea in care sunt descoperite
///pmin -> reprezinta cel mai mic nivel pe care se afla un nod din stiva
///viz -> reprezinta starea de vizitare a unui nod
struct{
    int ind, pmin;
    bool viz;
    }v[1000];

int cnt;

///algoritmul lui Tarjan
void ctc(int x)
{
    ///se memoreaza nivelul pe care se afla un nod in parcurgerea DFS, pornind din nodul de start cu care am intrat in functie
    ///contorul corespunde nivelului pe care se afla nodul curent in parcurgerea DFS
    v[x].ind = cnt;
    v[x].pmin = cnt;
    cnt++;
    int u;
    ///punem pe stiva nodurile in ordinea in care sunt vizitate pentru a tine evidenta
    s.push(x);
    ///marcam nodul ca vizitat
    v[x].viz = true;
    ///iteram prin fiecare nod care se afla in lista de adiacenta a nodului curent
    for(auto it: l[x])
        ///in cazul in care indicele nivelului pe care se afla este -1(nu l-am determinat) atunci parcurgem recursiv functia cu
        ///nodul curent ca parametru, iar nivelul minim pe care s-a aflat nodul pentru care iterez prin lista de adiacenta devine
        ///minimul dintre nivelele minime ale nodului actual si al sau
        if(v[it].ind == -1)
        {
            ctc(it);
            v[x].pmin = min(v[x].pmin, v[it].pmin);
        }
            ///altfel, daca nodul a fost vizitat atunci nivelul minim pe care s-a aflat nodul pentru care iterez prin lista de adiacenta
            ///devine minimul dintre nivelele minime ale nodului actual si al sau, dar fara a apela functia recursiv
            else if(v[it].viz)
                v[x].pmin = min(v[x].pmin, v[it].pmin);
    ///daca nivelul minim corespunde nivelului pe care am pus nodul atunci inseamna ca este radacina, deci iterez prin stiva care
    ///formeaza o componenta tare conexa, deci scot toate elementele din stiva si creez vectorul
    if(v[x].pmin == v[x].ind)
    {
        vect.clear();
        do
        {
            u = s.top();
            s.pop();
            v[u].viz = false;
            vect.push_back(u);
        }while(x != u);
        ///adaug componenta tare conexa in vectorul de componenete
        c.push_back(vect);
    }
}

int main()
{
    int n, m, x, y, i;
    in>>n>>m;
    ///creez lista de adiacenta
    while(m)
    {
        in>>x>>y;
        l[x].push_back(y);
        m--;
    }
    ///setez indicele pentru fiecare nod ca fiind -1, ceea ce inseamna ca nu l-am vizitat si nu stiu nivelul sau
    for(i = 1; i <= n; i++)
        v[i].ind = -1;
    ///caut noduri de inceput pentru componentele conexe, daca nivelul pe care se afla este inca -1
    for(i = 1; i <= n; i++)
        if(v[i].ind == -1)
            ctc(i);
    ///afisez
    for(auto it = 0; it < c.size(); it++)
    {
        for(auto it2: c[it])
            out<<it2<<" ";
        out<<endl;
    }
    return 0;
}