Cod sursa(job #2805854)

Utilizator namesurname01Name Surname namesurname01 Data 22 noiembrie 2021 02:41:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#include <vector>
#include <bitset>

using namespace std;
FILE* f, * g;

int m, n;
vector <int> graph[100002];
bitset <100002> fr;

void dfs(int nod)
{
    fr[nod] = 1;
    for (int i = 0;i < graph[nod].size();++i)
        if (!fr[graph[nod][i]])
            dfs(graph[nod][i]);
}
int main()
{
    f = fopen("dfs.in", "r");
    g = fopen("dfs.out", "w");
    fscanf(f, "%d %d", &n, &m);
    for (int i = 1;i <= m;++i)
    {
        int x, y;
        fscanf(f, "%d %d", &x, &y);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    int ss = 0;
    for (int i = 1;i <= n;++i)
        if (!fr[i]) ++ss, dfs(i);
    fprintf(g, "%d\n", ss);

    fclose(f);
    fclose(g);
    return 0;
}