Cod sursa(job #3332530)

Utilizator alex_codeTrifanescu Alexandru alex_code Data 7 ianuarie 2026 12:46:53
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 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[1001], low[1001], nr_comp;
bool inStiva[1001]={false};
vector<int>v[1001];
stack<int>sta;
vector<int>lot[1001];
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, g << "\n"){
        sort(lot[nr_comp].begin(), lot[nr_comp].end());
        for(const auto vecin:lot[i])
        g << vecin << " ";
    }

    return 0;
}