Cod sursa(job #3332535)

Utilizator alex_codeTrifanescu Alexandru alex_code Data 7 ianuarie 2026 13:12:49
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, loc, idx[100001], low[100001], nr_comp;
bool inStiva[100001]={false};
vector<int>v[100001];
stack<int>sta;
vector<int>lot[100001];
int timp;

void Tarjan(int nod){
    int i, e, s, cont=0;

    idx[nod]=low[nod]=++timp;
    sta.push(nod);
    inStiva[nod]=true;

    for(const auto vecin: v[nod]){
        if(idx[vecin]==0){
            Tarjan(vecin);
            low[nod]=min(low[nod], low[vecin]);
        }
        else{
            if(idx[vecin]!=0 && inStiva[vecin]==true){
                low[nod]=min(low[nod], idx[vecin]);

            }
        }
    }
    if(low[nod]==idx[nod]){
        nr_comp++;
        loc=-1;
        while(loc!=nod){
            loc=sta.top();
            sta.pop();
            inStiva[loc]=false;
            lot[nr_comp].push_back(loc);
        }
    }

}

int main(){

    int i, e, s, cont=0, a, b;
    f >> n >> m;
    for(i=1; i<=m; ++i)
    {
        f >> a >> b;
        v[a].push_back(b);
    }

    for(i=1; i<=n; ++i)
    {
        if(idx[i]==0){
            Tarjan(i);
        }

    }
    g << nr_comp << "\n";
    for(i=1; i<=nr_comp; ++i){
        sort(lot[i].begin(), lot[i].end());
        for(const auto vecin:lot[i])
            g << vecin << " ";
        g << "\n";
    }

    return 0;
}