Cod sursa(job #3259596)

Utilizator WiseAndrei4Vetrila Andrei WiseAndrei4 Data 26 noiembrie 2024 20:16:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dfs.in");
ofstream gout("dfs.out");
int n,m;
bool viz[100001];
vector<int>a[100001];
void citire()
{
    int x,y;
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y;
        a[x-1].push_back(y-1);
        a[y-1].push_back(x-1);
    }
}
void BFS(int nod)
{
    int crt;
    queue<int>q;
    q.push(nod);
    viz[nod]=1;
    while(!q.empty())
    {
        crt=q.front();
        for(int i=0; i<a[crt].size(); ++i)
            if(!viz[a[crt][i]])
            {
                viz[a[crt][i]]=1;
                q.push(a[crt][i]);
            }
        q.pop();
    }
}
int main()
{
    citire();
    int comp=0;
    for(int l=0; l<n; ++l)if(!viz[l])
        {
            ++comp;
            BFS(l);
        }
    gout<<comp;
    return 0;
}