Cod sursa(job #3005584)

Utilizator stefanscdStefan stefanscd Data 17 martie 2023 09:04:51
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,x,y,k,nrc;
vector<vector<int> > G,GT;
vector<int> viz,vizt,timp,comp;

void dfs(int nod){
    viz[nod]=1;
    for(auto t:G[nod])
        if(viz[t]==0)
            dfs(t);
    timp[++k]=nod;
}

void dfst(int nod){
    vizt[nod]=1;
    comp[nod]=nrc;
    for(auto t:GT[nod])
        if(vizt[t]==0)
            dfst(t);
}
void rezolvare(){
    for(int i=1;i<=n;++i)
        if(viz[i]==0)
            dfs(i);
    for(int i=n;i>=1;--i)
        if(vizt[timp[i]]==0)
            nrc++,dfst(timp[i]);
}
int main()
{
    fin>>n>>m;
    G=GT=vector<vector<int> > (m+1);
    viz=vizt=timp=comp=vector<int> (n+1);
    for(int i=1;i<=m;++i){
        fin>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    rezolvare();
    fout<<nrc<<'\n';
    for(int i=1;i<=nrc;++i,fout<<'\n')
        for(int j=1;j<=n;++j)
            if(comp[j]==i)
                fout<<j<<" ";
    return 0;
}