Cod sursa(job #2856416)

Utilizator m1i2h3a4i5Popescu Adrian Mihai m1i2h3a4i5 Data 23 februarie 2022 20:17:31
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include<fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int v[200002],v2[200002],x[2000][2000],viz[200002],i,j,nr1,nr2,nctc,n,m;
void dfs1(int a){
    int i;
    v[a]=1;
    for(i=1;i<=n;i++){
        if(v[i]==0&&x[a][i]==1){
            dfs1(i);
        }
    }
}
void dfs2(int a){
    int i;
    v2[a]=1;
    for(i=1;i<=n;i++){
        if(v2[i]==0&&x[i][a]==1){
            dfs2(i);
        }
    }
}
int main ()
{
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>nr1>>nr2;
        x[nr1][nr2]=1;
    }
    nctc=0;
    for(i=1;i<=n;i++){
        if(viz[i]==0){
            nctc++;
            dfs1(i);
            dfs2(i);
            for(j=1;j<=n;j++){
                if(v[j]==1&&v2[j]==1){
                    viz[j]=nctc;
                }
                v[j]=0;
                v2[j]=0;
            }
        }
    }
    fout<<nctc<<'\n';
    for(int k=1;k<=nctc;k++){
        for(i=1;i<=n;i++){
            if(viz[i]==k){
                fout<<i<<" ";
            }
        }
        fout<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}