Cod sursa(job #3161859)

Utilizator chesadavidChesa David chesadavid Data 28 octombrie 2023 09:40:54
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

int n,m;
long  a[1000][1000];

void citire(){
    int x,y;
for(int i=1;i<=m;i++){
    f>>x>>y;
    a[x][y]=1;
}
}
int vt[1000]={0};
int c[1000];
int parcurgere(int vf){
    int pi=0;
    int pf =0;
    c[pf]=vf;
    vt[vf]=1;
    while(pi <= pf){
        int h=c[pi];
        for(int i=1;i<=n;i++){
                if(a[h][i]==1 && vt[i]==0){
                    pf++;
                    c[pf]=i;
                    vt[i]=1;
                }
        }
        pi++;
    }

}

int main()
{   f>>n>>m;
    int comp=0;
    citire();
    for(int i=1;i<=n;i++){
        if(vt[i]==0){
            parcurgere(i);
            comp++;

        }
    }
    g<<comp;
    return 0;
}