Cod sursa(job #3317007)

Utilizator Mirc100Mircea Octavian Mirc100 Data 21 octombrie 2025 17:40:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include<bits/stdc++.h>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector<int>G[100005];
vector<int>Gt[100005];
vector<int>nrc[100005];

int n,m;

int viz[100005];
stack<int>st;
int nrctc;

void DFS(int x){
    viz[x]=true;
    for (auto &y:G[x])
        if (viz[y]==false) DFS(y);
    st.push(x);
}

void DFST(int x){
    viz[x]=true;
    nrc[nrctc].push_back(x);
    for (auto &y:Gt[x])
        if (viz[y]==false) DFST(y);
}

int main()
{
    f>>n>>m;
    for (int i=1;i<=m;i++){
        int x, y;
        f>>x>>y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }

    for (int i=1;i<=n;i++)
        if (viz[i]==false)
            DFS(i);

    memset(viz,0,sizeof(viz));

    while (!st.empty()){
        int i=st.top();
        st.pop();
        if (viz[i]==false){
            nrctc++;
            DFST(i);
        }
    }

    g<<nrctc<<'\n';
    for (int i=1;i<=nrctc;i++){
        for (auto &nod:nrc[i])
            g<<nod<<" ";
        g<<'\n';
    }
    return 0;
}