Cod sursa(job #2668619)

Utilizator OrzataAndreiOrzata Andrei OrzataAndrei Data 5 noiembrie 2020 04:37:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#define MAX 100010

using namespace std;

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

typedef struct nod
{
    int x;
    nod *a;

} *ptr_Nod;


int N, M, Viz[MAX], nr;
ptr_Nod Graf[MAX];

void add(ptr_Nod &aux, int val)
{
    ptr_Nod ptr;
    ptr = new nod;
    ptr -> x = val;
    ptr -> a = aux;
    aux = ptr;
}

void citire()
{

    in>>N>>M;
    int i, x, y;

    for (i = 1; i <= M; i++)
    {
        in>>x>>y;
        add(Graf[x], y);
        add(Graf[y], x);
    }
}

void DFS(int nod)
{
    ptr_Nod ptr;
    Viz[nod] = 1;
    for (ptr = Graf[nod]; ptr != NULL; ptr = ptr -> a)
        if (!Viz[ptr -> x])
            DFS(ptr -> x);
}


int main()
{
    citire();
    for (int i = 1; i <= N; i++)
        if (!Viz[i])
        {
            nr++;
            DFS(i);
        }
    out<<nr<<"\n";
    return 0;
}