Cod sursa(job #2925944)

Utilizator gizzehhhAsavoaei Bianca Gabriela gizzehhh Data 16 octombrie 2022 14:13:25
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <fstream>
#include <iostream>
#include <bits/stdc++.h>
#define N 100005
#define M 200005

using namespace std;

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

vector < vector <int>> l(N);
vector <int> stkItem(N);
vector <int> disc(N) , lowLink(N);
stack <int> stk;
vector < vector <int>> sol(N);


int n, m, i, j, x, y, ct;
int t;


void Input(){
    cin >> n >> m;
    for(i=1; i<=m; i++)
    {
        cin >> x >> y;
        l[x].push_back(y);
    }
}

void findComponent(int node){

    stk.push(node);
    stkItem[node] = 1;
    disc[node] = lowLink[node] = ++t;



    for( i = 0; i < l[node].size(); i++){

        int v = l[node][i];
        if(disc[v] == 0)
                  findComponent(v);

        if(stkItem[v])
                      lowLink[node] = min (lowLink[node], lowLink[v]);

    }


     int poppedItem = 0;
     if(lowLink[node] == disc[node]){
         while(stk.top() != node) {
             poppedItem = stk.top();
             stkItem[poppedItem] = 0;
             lowLink[poppedItem] = disc[node];
             stk.pop();
         }

         poppedItem = stk.top();
         stkItem[poppedItem] = 0;
         lowLink[poppedItem] = disc[node];
         stk.pop();

         ct ++;
     }




}

void SCC(){

    for(i = 1; i <= n; i++)
          if(disc[i] == 0)
              findComponent(i);

    for(i = 1; i <= n; i++)
    {
        sol[lowLink[i]].push_back(i);
    }


    cout << ct <<"\n";

    for(i = 1; i <= n; i++) {
        if(sol[i].size())
        {
             for(j = 0; j < sol[i].size(); j++)
                    cout << sol[i][j] <<" ";

        }

        cout <<"\n";
    }


}

int main()
{
    Input();
    SCC();


    return 0;
}