Cod sursa(job #2544231)

Utilizator NoodlesAndi Domnulete Noodles Data 11 februarie 2020 20:59:49
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>

using namespace std;


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

int N, M, i, j, x, y;
int a[20000][20000];
int viz[20000];


void dfs(int nr){
    int i;
    viz[nr] = 1;
    for(i = 1; i <= N; i++){
        if(a[nr][i] == 1 && viz[i] == 0){
            dfs(i);
        }
    }
}

int main()
{
    int rez = 0;

    f >> N >> M;

    for(i = 1; i <= M; i++){
        f >> x >> y;
        a[x][y] = 1;
        a[y][x] = 1;
    }

    for(i = 1; i <= N; i++){
        viz[i] = 0;
    }

    for(i = 1; i <= N; i++){
        if(viz[i] == 0){
            dfs(i);
            rez++;
        }
    }

    f2 << rez;

    return 0;
}