Cod sursa(job #3228563)

Utilizator 1gbr1Gabara 1gbr1 Data 8 mai 2024 20:37:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> G[100001], T[100001];
stack<int> st;
bitset<100001> viz;

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

void DFS1(int nod)
{
    viz[nod] =  1;
    for (auto& next : G[nod])
        if (!viz[next])
            DFS1(next);
    st.push(nod);
}

vector<vector<int> > ctc;

void DFS2(int nod)
{
    viz[nod] = 1;
    ctc.back().push_back(nod);
    for (auto next : T[nod])
        if (!viz[next])
            DFS2(next);
}

int main() {
    int n, m;
    fin >> n >> m;
    while (m--) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        T[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
        if (!viz[i])
            DFS1(i);
    viz.reset();
    while (!st.empty()) {
        if (!viz[st.top()]) {
            ctc.push_back({});
            DFS2(st.top());
        }
        st.pop();
    }
    fout << ctc.size() << "\n";
    for (auto &cc: ctc)
    {
        for (auto& el : cc)
            fout << el << " ";
        fout << "\n";
    }
    return 0;
}