Cod sursa(job #3370376)

Utilizator alex_0747Gheorghica Alexandru alex_0747 Data 25 octombrie 2026 20:21:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;

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

int n, m, nrc;
vector<int> L[100005], Lt[100005], ans[100005];
bitset<100005> v;
stack<int> st;

void DFS(int k)
{
    v[k] = 1;
    for (int i : L[k]) {
        if (!v[i]) {
            DFS(i);
        }
    }
    st.push(k);
}

void DFSt(int k) 
{
    v[k] = 1;
    ans[nrc].push_back(k);
    for (int i : Lt[k]) {
        if (!v[i]) {
            DFSt(i);
        }
    }
}

int main()
{
    int i, j;
    fin >> n >> m;
    while (m--) {
        fin >> i >> j;
        L[i].push_back(j);
        Lt[j].push_back(i);
    }
    
    for (int i = 1; i <= n; i++) {
        if (!v[i]) {
            DFS(i);
        }
    }

    v.reset();
    while (!st.empty()) {
        i = st.top();
        st.pop();
        if (v[i]) continue;
        DFSt(i);
        nrc++;
    }

    fout << nrc << "\n";
    for (int i = 0; i < nrc; i++) {
        for (int j : ans[i]) {
            fout << j << " ";
        }
        fout << "\n";
    }
    return 0;
}