Cod sursa(job #2925580)

Utilizator Nicolae11Mihaila Nicolae Nicolae11 Data 15 octombrie 2022 18:51:32
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,k,low_link[100005],pe_stiva[100005],viz[100005];
stack<int> stiva;
vector<int> liste[100005],afisare[100005];

void Tarjan(int curent)
{
    stiva.push(curent);
    pe_stiva[curent]=1;
    low_link[curent]=curent;
    viz[curent]=1;
    for(auto j : liste[curent])
    {
        if(viz[j]==0)
            Tarjan(j);
        if(pe_stiva[j]==1)
            low_link[curent]=min(low_link[curent],low_link[j]);
    }
    if(low_link[curent]==curent)
    {
        k++;
        int aux=stiva.top();
        while(aux!=curent)
        {
            pe_stiva[aux]=0;
            low_link[aux]=curent;
            afisare[k].push_back(aux);
            stiva.pop();
            aux=stiva.top();
        }
        pe_stiva[curent]=0;
        afisare[k].push_back(aux);
        stiva.pop();
    }
    return;
}
int main()
{   f>>n>>m;
    int st,dr;
    for(int i=1;i<=m;i++)
    {   f>>st>>dr;
        liste[st].push_back(dr);
    }
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
            Tarjan(i);
    g<<k<<'\n';
    for(int i=1;i<=k;i++)
    {   for(auto j : afisare[i])
            g<<j<<' ';
        g<<'\n';
    }
    f.close();
    g.close();
    return 0;
}