Cod sursa(job #2925344)

Utilizator bogdan.schiopBogdan Schiop bogdan.schiop Data 14 octombrie 2022 19:50:48
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

int viz[10001];
int dist[10001];
int n, m, s, conexe;
int a[10001][10001];

void citire()
{
    fin >> n >> m;
    int aux1, aux2;
    for(int i = 1; i <= m ; i++)
    {
        fin >> aux1 >> aux2;
        a[aux1][aux2]= 1;
        a[aux2][aux1]= 1;
    }
    /*for(int i = 1 ; i <= n ; i++)
        dist[i] = -1;*/
}

deque<int> q;

void BFS()
{
    q.push_back(s);
    viz[s] = 1;
    dist[s] = 0;
    while(!q.empty())
    {
        for(int i = 1; i <= n ; i++)
        {
            if(a[q.front()][i] == 1 && !viz[i])
            {
                q.push_back(i);
                viz[i] = 1;
                dist[i] = dist[q.front()]+1;
            }
        }
        q.pop_front();
    }
}

void DFS(int nod)
{
    viz[nod] = 1;
    for(int i = 1 ; i <= n ; i++)
    {
        if(a[nod][i] == 1 && !viz[i])
            DFS(i);
    }
}

int main()
{
    citire();
    for(int i = 1 ; i <= n ; i++)
    {
        if(viz[i] == 0)
        {
            DFS(i);
            conexe++;
        }
    }
    cout << conexe;
    return 0;
}