Cod sursa(job #3346621)

Utilizator raultimarTimar Raul raultimar Data 14 martie 2026 17:03:26
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m,i,j,x,y,nrc;
bool viz[100001];
stack<int>st;
set<int>v[100000];
set<int>vt[100000];
set<int>sol[100000];
void dfs1(int x){
     viz[x]=1;
     for(auto y:v[x]){
        if(viz[y]==0) dfs1(y);
     }
     st.push(x);
}
void dfs2(int x){
     sol[nrc].insert(x);
     viz[x]=1;
     for(auto y:vt[x]) if(viz[y]==0) dfs2(y);
}
int main()
{
    in>>n>>m;
    for(i=1;i<=m;i++){
        in>>x>>y;
        v[x].insert(y);
        vt[y].insert(x);
    }
    for(i=1;i<=n;i++){
        if(viz[i]==0) dfs1(i);
    }
    for(i=1;i<=n;i++) viz[i]=0;
    while(!st.empty()){
         x=st.top();
         st.pop();
         if(viz[x]==0){
            nrc++;
            dfs2(x);
         }
    }
    out<<nrc<<"\n";
    for(i=1;i<=nrc;i++){
        for(auto k:sol[i]){
            out<<k<<" ";
        }
        out<<"\n";
    }
    return 0;
}