Cod sursa(job #2196137)

Utilizator horea4Cenan Horea horea4 Data 18 aprilie 2018 16:54:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector <int> v[100001];
bool vizita[100001];
queue <int> q;
int N,M,a,b,rez;
void bfs(int n)
{
    q.push(n);
    vizita[n]=1;
    while(!q.empty())
    {
        for(auto i:v[q.front()])
        {
            if(vizita[i]==0)
            {
                vizita[i]=1;
                q.push(i);
            }
        }
        q.pop();

    }
}
int main()
{   fin>>N>>M;
for(int i=1;i<=M;i++)
{  fin>>a>>b;
   v[a].push_back(b);
   v[b].push_back(a);

}
for(int i=1;i<=N;i++)
{
    if(vizita[i]==0)
    {
        rez++;
        bfs(i);
    }
}
fout<<rez;

    return 0;
}