Cod sursa(job #2924661)

Utilizator DafinaTrufasTrufas Dafina DafinaTrufas Data 7 octombrie 2022 20:09:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int v[100001], n, m, nr;
vector <int> l[100001];

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

void df (int vf)
{
    int i;
    v[vf] = nr;
    for (i = 0; i < l[vf].size(); i++)
        if (v[l[vf][i]] == 0)
            df(l[vf][i]);
}

int main()
{int i, j, k;
f >> n >> m;
for (k = 1; k <= m; k++)
{
    f >> i >> j;
    l[i].push_back(j);
    l[j].push_back(i);
}
for (i = 1; i <= n; i++)
    if (v[i] == 0)
    {
        nr++;
        df(i);
    }
g << nr;
return 0;
}