Cod sursa(job #3374096)

Utilizator nic150Musat Nicoleta nic150 Data 8 noiembrie 2026 17:41:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb

// complexitate O(n+m)
#include <iostream>
#include<vector>
#include<stack>
#include<fstream>
using namespace std;

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

vector<int> g[100001], gt[100001];
vector<int> componente[100001];

bool viz[100001];
stack<int> st;

int n, m, nrCTC=0;

void dfs1(int nod) {
    viz[nod]=true;

    for (int vecin : g[nod]) {
        if (!viz[vecin]) 
            dfs1(vecin);
    }
    st.push(nod);
}

void dfs2(int nod) {
    viz[nod]=true;
    componente[nrCTC].push_back(nod);

    for (int vecin : gt[nod]) {
        if (!viz[vecin]) {
            dfs2(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++) {
        if (!viz[i]) {
            dfs1(i);
        }
    }

    const int sviz=sizeof(viz);

    for(int i=1;i<=sviz;i++)
        viz[i]=false;

    while (!st.empty()) {
        int nod=st.top();
        st.pop();

        if (!viz[nod]) {
            nrCTC++;
            dfs2(nod);
        }
    }

    fout << nrCTC << '\n';

    for (int i=1; i <= nrCTC; i++) {
        for (int nod : componente[i]) {
            fout << nod << " ";
        }
        fout << '\n';
    }

    return 0;
}