Cod sursa(job #2978439)

Utilizator Bogdan-AlxDinca Bogdan-Alexandru Bogdan-Alx Data 13 februarie 2023 19:07:48
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
using namespace std;
ofstream fout("bfs.out");
ifstream fin("bfs.in");
int n,m,start[100002],viz[100002],s,x,y,coada[100002],pr,ul,nr,nrr;
struct {
    int vecin,leg;
} L[400002];


int main() {
    fin >> n >> m;
    int k=0;
    for (int i = 1; i <= m; ++i) {
        fin >> x >> y;
        k++;
        L[k].vecin=y;
        L[k].leg=start[x];
        start[x]=k;
        k++;
        L[k].vecin=x;
        L[k].leg=start[y];
        start[y]=k;
    }
    for (int i = 1; i <= n; ++i) {
        if(viz[i]==0) {
            s=i;
            coada[1]=s;
            viz[s]=1;
            pr=1;
            ul=1;
            nr=1;
            while (nr > 0) {
                x = coada[pr];
                for (int i = start[x]; i != 0; i = L[i].leg) {
                    y = L[i].vecin;
                    if (viz[y] == 0) {
                        viz[y] = 1;
                        ul++;
                        coada[ul] = y;
                        nr++;
                    }
                }
                pr++;
                nr--;
            }
            nrr++;
        }
    }
    fout << nrr;
    return 0;
}