Cod sursa(job #3373957)

Utilizator laur7766laur m laur7766 Data 8 noiembrie 2026 12:37:23
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

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

int N, M, ctc;
int vizitat[100005];
vector<int> G[100005];
vector<int> GT[100005];
set<pair<int, int>> ctcs;
stack<int> S;

void DFS(int Nod) {
    vizitat[Nod] = 0;
    for(auto vecin : G[Nod]) {
        if(vizitat[vecin]) {
            DFS(vecin);
        }
    }
    S.push(Nod);
}

void DFST(int Nod) {
    vizitat[Nod] = ctc;
    for(auto vecin : GT[Nod]) {
        if(!vizitat[vecin]) {
            DFST(vecin);
        }
    }
}

int main()
{
    fin >> N >> M;
    for(int i = 0; i < M; ++i) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    
    for(int i = 1; i <= N; ++i) {
        vizitat[i] = -1;
    }
    
    for(int i = 1; i <= N; ++i) {
        if(vizitat[i] == -1) {
            DFS(i);
        }
    }
    
    while(!S.empty()) {
        int Nod = S.top();
        S.pop();
        
        if(vizitat[Nod] < 1) {
            ++ctc;
            DFST(Nod);
        }
    }
    
    fout << ctc;
    for(int i = 1; i <= N; ++i) {
        ctcs.insert({vizitat[i], i});
    }

    int count_ctc = 0;
    for(const auto& elem : ctcs) {
        if(elem.first != count_ctc) {
            count_ctc = elem.first;
            fout << endl;
        }
        fout << elem.second << ' ';
    }
    
    return 0;
}