Cod sursa(job #3258302)

Utilizator Mocanu_Tudor_CristianMocanu Tudor Cristian Mocanu_Tudor_Cristian Data 21 noiembrie 2024 19:56:09
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int n, m, x, y, v[1001][1001], viz[1001], cnt;

void DFS(int i)
{
    viz[i] = 1;
    for(int j = 1; j <= n; j++)
    {
        if(v[i][j] == 1 && viz[j] == 0)
        {
            viz[j] = 1;
            DFS(j);
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        v[x][y] = 1;
        v[y][x] = 1;
    }
    for(int i = 1; i <= n; i++)
    {
        if(viz[i] == 0)
        {
            cnt++;
            DFS(i);
        }
    }
    fout << cnt;

    return 0;
}