Cod sursa(job #3271050)

Utilizator alexsavinAlexandru Stefan Savin alexsavin Data 25 ianuarie 2025 09:43:34
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;

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

int n,i,y,m,cnt,x;
vector<int>v[100005],g[100005],p[100005];
deque<int>q;
bool viz[100005];

void dfs(int k){
   viz[k]=1;

   for(auto i : v[k])
    if(!viz[i])
    dfs(i);

   q.push_back(k);

}

void dfsg(int k,int n){

 viz[k]=1;
 p[cnt].push_back(k);

 for(auto i : g[k])
    if(!viz[i])
    dfsg(i,n);
}

int main(){

   fin>>n>>m;

   for(i=1;i<=m;i++){
    fin>>x>>y;
    v[x].push_back(y);
    g[y].push_back(x);
   }

   for(i=1;i<=n;i++)
     if(!viz[i])dfs(i);

     for(i=1;i<=n;i++)viz[i]=0;

   for(auto it=q.rbegin();it!=q.rend();it++){

    if(!viz[*it]){
            cnt++;
            dfsg(*it,cnt);
    }
   }
   fout<<cnt<<'\n';

   for(i=1;i<=cnt;i++,fout<<'\n')
    for(auto y : p[i])
    fout<<y<<" ";

}