Cod sursa(job #3280244)

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

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

 vector<int> G[100005] , componente[100005];
 stack <int> s;
 int n , m;
 int low[100005] , num[100005];
 bool v[100005] , on_stack[100005];
 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';
     }
 }