Cod sursa(job #3343976)

Utilizator ana_maria_772Toc Ana-Maria ana_maria_772 Data 28 februarie 2026 20:41:32
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

int n, m, vizitat[100001], nrc;
vector <int> vecini[100001], transpusa[100001];
stack <int> st;
set <int> rez[100001];

void DFS(int nod) {
    vizitat[nod]= 1;
    for (auto next : vecini[nod])
        if (!vizitat[next])
            DFS(next);
    st.push(nod);
}

void DFS_T(int nod) {
    vizitat[nod]= 2;
    rez[nrc].insert(nod);
    for (auto next : transpusa[nod])
        if (vizitat[next]==1)
            DFS_T(next);
}

int main() {
    cin>>n>>m;
    while (m--)
    {
        int i, j;
        cin>>i>>j;
        vecini[i].push_back(j);
        transpusa[j].push_back(i);
    }
    for (int i=1; i<=n; i++)
        if (!vizitat[i])
            DFS(i);
    while (!st.empty())
    {
        int nod= st.top();
        st.pop();
        if (vizitat[nod]==1)
        {
            nrc++;
            DFS_T(nod);
        }
    }
    cout<< nrc <<"\n";
    for (int i=1; i<=nrc; i++, cout<<"\n")
        for (auto x : rez[i])
            cout<< x <<" ";
    return 0;
}