Cod sursa(job #3280242)

Utilizator GabyXBBabiuc Eduard Gabriel GabyXB Data 25 februarie 2025 21:35:10
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
 ///tarjan tuti tarzanu mati...
 #include <iostream>
 #include <vector>
 #include <stack>
 using namespace std;

 vector<int> G[105] , componente[105];
 stack <int> s;
 int n , m;
 int low[105] , num[105];
 bool v[105] , on_stack[105];
 int index , nrc;

 void citire()
 {
     int x , y;
     cin >> n >> m ;
     for(int i = 1 ; i<=m ; ++i)
     {
         cin >> x>>y;
         G[x].push_back(y);
     }
 }

 void dfs(int nod)
 {
     v[nod] = 1;     on_stack[nod] = 1;
     index++;
     num[nod] = low[nod] = index;
     s.push(nod);

     for(auto e : G[nod])
        if(!v[e])
        {
            dfs(e);
            low[nod] = min(low[nod] , low[e]);
        }
        else if(on_stack[e]) low[nod] = min(low[nod] , low[e]);

    if(num[nod] == low[nod])
    {
        nrc++;
        while(s.top() != nod)
        {
            componente[nrc].push_back(s.top());
            on_stack[s.top()] = 0 ;
            s.pop();
        }
        s.pop();
        on_stack[nod] = 0 ;
        componente[nrc].push_back(nod);
    }
 }

 int main()
 {
     citire();
     for(int i = 1 ; i<= n ; ++i)
        if(!v[i])
            dfs(i);

    cout << nrc << '\n';
     for(int i = 1 ; i<=nrc ; ++i)
     {
         for(auto e : componente[i])
            cout << e << ' ';
         cout << '\n';
     }
 }