Cod sursa(job #3122952)

Utilizator daria.swDaria Lebada daria.sw Data 21 aprilie 2023 13:07:53
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>

using namespace std;

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

int n, s[10001], A[10001][10001], v[10001], k;

void citire()
{
    int x, y;
    fin >> n;
    while (fin >> x >> y)
        A[x][y] = A[y][x] = 1;
}

void DFS(int x, int nr)
{
    s[x] = nr;
    for (int j = 1; j <= n; j++)
        if (A[x][j] == 1 && s[j] == 0)
            DFS(j, nr);
}

int main()
{
    citire();
    int nr = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!s[i])
        {
            nr++;
            DFS(i, nr);
        }
    }
    fout << nr;

    return 0;
}