Cod sursa(job #3030865)

Utilizator SamurayxJackDiaconescu Octavian SamurayxJack Data 17 martie 2023 22:27:50
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include<bits/stdc++.h>
using namespace std;

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

const int Nmax=1e5+1;

int n,m,viz[Nmax],nr;
vector<int>G[Nmax],H[Nmax];
stack<int>S;

void DFS1(int x){
    viz[x]=1;
    for(auto v:G[x]) if(!viz[v]) DFS1(v);
    S.push(x);
}

void DFS2(int x){
    viz[x]=nr;
    for(auto v:H[x]) if(!viz[v]) DFS2(v);
}

int main(){
    int a,b;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>a>>b;
        G[a].push_back(b);
        H[b].push_back(a);
    }
    DFS1(1);
    for(int i=1;i<=n;i++) viz[i]=0;
    while(!S.empty()){
        int x=S.top();
        S.pop();
        if(!viz[x]) ++nr,DFS2(x);
    }
    fout<<nr<<'\n';
    for(int i=1;i<=nr;i++){
        for(int j=1;j<=n;j++)
         if(viz[j]==i) fout<<j<<" ";
        fout<<'\n';
    }
    return 0;
}