Cod sursa(job #2839359)

Utilizator xXoctavianXxStanescu Matei Octavian xXoctavianXx Data 25 ianuarie 2022 20:22:37
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax=1e5+5;
int n,m,indecs=1;
vector<int> vecini[nmax];
int idx[nmax],lowlink[nmax];
stack<int> S;
bool in_stack[nmax];
vector<vector<int> > C;

void tarjan(int nod)
{
    idx[nod]=indecs;
    lowlink[nod]=indecs;
    indecs++;
    S.push(nod);
    in_stack[nod]=true;
    for(auto pi: vecini[nod])
    {
        if(idx[pi]==0)
        {
            tarjan(pi);
            lowlink[nod]=min(lowlink[nod],lowlink[pi]);
        }
        else if(in_stack[pi])
        {
            lowlink[nod]=min(lowlink[nod],lowlink[pi]);
        }
    }
    if(lowlink[nod]==idx[nod])
    {
        vector<int> comp;
        int i;
        do{
            i=S.top();
            comp.push_back(i);
            in_stack[i]=0;
            S.pop();
        }while(i!=nod);
        C.push_back(comp);
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int a,b;
        fin>>a>>b;
        vecini[a].push_back(b);
    }
    for(int i=1; i<=n; i++)
    {
        if(idx[i]==0)
        {
            tarjan(i);
        }
    }
    fout<<C.size()<<"\n";
    for(int i=0; i<C.size(); i++)
    {
        for(auto el : C[i]) fout<<el<<" ";
        fout<<"\n";
    }
    return 0;
}