Cod sursa(job #2756490)

Utilizator alexandra.buruianaAlexandra Buruiana alexandra.buruiana Data 1 iunie 2021 01:16:55
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <set>
using namespace std;
ifstream fin("ctc.in");
ifstream fout("ctc.out");
int A[100][100],x,postordine[100],viz[100],n,m,y,nr=0,nrm=0,vfs=0,vfMax=0,prag=0,AT[100][100];

//sortare topologica
void dfs (int x){
    
    
    viz[x]=1;
    //cout<<x<<" ";
    for(int i=1;i<=A[x][0];i++)
        if(viz[A[x][i]]==0){
            dfs(A[x][i]);
        }
    postordine[++nr]=x;
}
void dfst (int x, int root){
    
    
    viz[x]=0-root;
    //cout<<x<<" ";
    for(int i=1;i<=AT[x][0];i++)
        if(viz[AT[x][i]]>0){
            dfst(AT[x][i],root);
        }
    
}
void dfst2 (int x){
    
    
    viz[x]=1;
    fout<<x<<" ";
    for(int i=1;i<=AT[x][0];i++)
        if(viz[AT[x][i]]<1){
            dfst2(AT[x][i]);
        }
    
}
int main()
{
    fin>>n;
    fin>>m;
    for(int i=0;i<m;i++)
        {
            fin>>x>>y;
            A[x][0]++;
            A[x][A[x][0]]=y;
            AT[y][0]++;
            AT[y][A[y][0]]=x;
        }
    for(int i=1;i<=n;i++){
        if(!viz[i]){
            dfs(i);
        }
    }
    // for(int i=n;i>0;i--)
    //     cout<<postordine[i]<<" ";

    for(int i=n;i>0;i--){
        if(viz[postordine[i]]>0){
            nrm++;
            dfst(postordine[i],nrm);
            //cout<<'\n';
        }
    }
    // for(int i=n;i>0;i--)
    //     cout<<viz[i]<<" ";
    
    fout<<nrm;
    fout<<'\n';
    for(int i=n;i>0;i--){
        if(viz[postordine[i]]<0){
            //nrm++;
            dfst2(postordine[i]);
            fout<<'\n';
        }
    }
    return 0;
}