Cod sursa(job #2757769)

Utilizator MoarcascosminMoarcas Cosmin Moarcascosmin Data 6 iunie 2021 14:17:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>

using namespace std;

int n, m, vizitat[100001], numar;

struct Node
{
    int data;
    Node *next;
}*vecini[100001];

void Adaugare(int nod, int vecin)
{
    Node *p = new Node;
    p->data = vecin;
    p->next = vecini[nod];
    vecini[nod] = p;
}

void Citire()
{
    ifstream f("dfs.in");

    int nod1, nod2;

    f >> n >> m;

    for(int i = 0; i < m; i++)
    {
        f >> nod1 >> nod2;
        Adaugare(nod1, nod2);
        Adaugare(nod2, nod1);
    }
}

void Dfs(int varf)
{
    vizitat[varf] = 1;
    Node *p = vecini[varf];

    while(p)
    {
        if(!vizitat[p->data])
            Dfs(p->data);
        p = p->next;
    }
}

void DeterminareNumarComponente()
{
    for(int i = 1; i <= n; i++)
        if(!vizitat[i])
        {
            numar++;
            Dfs(i);
        }
}

void Afisare()
{
    ofstream g("dfs.out");
    g << numar;
}

int main()
{
    Citire();
    DeterminareNumarComponente();
    Afisare();

    return 0;
}