Cod sursa(job #3268993)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 18 ianuarie 2025 10:07:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <bits/stdc++.h>
#define in fin
#define out fout

using namespace std;

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

vector<int> v[100001];
stack<int> s;
int low[100001];
int id[100001];
bool in_stiva[100001];
vector< vector<int> > ctc;
int it = 1;

void dfs(int nod){
    if(id[nod] != 0) return;
    // cout << "Am ajuns in dfs la : " << nod << '\n';
    id[nod] = low[nod] = it;
    it++;
    s.push(nod);
    in_stiva[nod] = 1;

    // cout << "Calculam LOW pentru : " << nod << " ( id = " << id[nod] << " )\n";
    for(int cop : v[nod]){
        if(id[cop] == 0 && !in_stiva[cop]){
            // cout << "  -- > luam in considerare : " << cop << '\n';
            dfs(cop);
            low[ nod ] = min(low[nod], low[ cop ]);
        }else if(in_stiva[cop]){
            low[ nod ] = min(low[nod], low[ cop ]);
        }
    }
    // cout << "LOW pentru : " << nod << " este : " << low[nod] << '\n';

    if(low[nod] == id[nod] && in_stiva[nod]){
        // cout << "------\n";
        vector<int> c;
        while(true){
            int node = s.top();
            // cout << "Scoatem " << node << '\n';
            c.push_back( node );
            in_stiva[ node ] = 0;
            s.pop();
            if(node == nod) break;
        }
        ctc.push_back(c);
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m; in >> n >> m;
    for(int i = 0; i < m; i++){
        int l, r; in >> l >> r;
        v[l].push_back(r);
    }

    for(int i = 1; i <= n; i++){
        if(!in_stiva[i]){
            dfs(i);
        }
    }

    out << ctc.size() << '\n';
    for(int i = 0; i < ctc.size(); i++){
        sort(ctc[i].begin(), ctc[i].end());
        for(int j = 0; j < ctc[i].size(); j++) out << ctc[i][j] << " ";
        out << '\n';
    }

    return 0;
}