Cod sursa(job #2805856)

Utilizator namesurname01Name Surname namesurname01 Data 22 noiembrie 2021 02:41:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <deque>

using namespace std;
FILE* fin, * fout;

int start[100002], t[2][400002];
bool viz[100002];
deque <int>flu;
void ddfs(int nod)
{
    flu.push_back(nod);
    viz[nod] = 1;
    while (!flu.empty()) {
        nod = flu.front();
        flu.pop_front();
        int p;
        p = start[nod];
        while (p) {
            if (viz[t[0][p]] == 0)
                viz[t[0][p]] = 1, flu.push_back(t[0][p]);
            p = t[1][p];
        }
    }
}
int main()
{
    int n, m, x, y, k = 0;
    fin = fopen("dfs.in", "r");
    fout = fopen("dfs.out", "w");
    fscanf(fin, "%d %d", &n, &m);
    for (int i = 1;i <= m;++i) {
        fscanf(fin, "%d %d", &x, &y);
        t[0][++k] = y;
        t[1][k] = start[x];
        start[x] = k;

        t[0][++k] = x;
        t[1][k] = start[y];
        start[y] = k;
    }
    int da = 0;
    for (int i = 1;i <= n;++i)
        if (viz[i] == 0) ++da, ddfs(i);
    fprintf(fout, "%d", da);

    return 0;
}