Cod sursa(job #2805853)

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

using namespace std;
FILE* f, * g;
int start[100002], t[3][400004];
bitset <100002>viz;
deque <int> q;
int ss, m, n;

void dfs(int nod)
{
    int no;
    viz[nod] = 1;
    no = start[nod];
    while (no)
    {
        if (!viz[t[0][no]])
            dfs(t[0][no]);
        no = t[1][no];
    }
}

void noduri()
{
    int i;
    for (i = 1;i <= n;++i)
    {
        if (viz[i] == 0)
        {
            ++ss;
            dfs(i);
        }
    }
}

int main()
{
    int i, j, o, k = 0, nod, no;
    f = fopen("dfs.in", "r");
    g = fopen("dfs.out", "w");
    fscanf(f, "%d %d", &n, &m);
    for (o = 1;o <= m;++o)
    {
        fscanf(f, "%d %d", &i, &j);
        ++k;
        t[0][k] = j;
        t[1][k] = start[i];
        start[i] = k;
        ++k;
        t[0][k] = i;
        t[1][k] = start[j];
        start[j] = k;
    }
    noduri();
    fprintf(g, "%d", ss);
    fclose(f);
    fclose(g);
    return 0;
}