Cod sursa(job #1766049)

Utilizator filip.mihalutMihalut Filip filip.mihalut Data 27 septembrie 2016 12:43:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

int x,poz,n,m,i,y,k;
queue < int > Q;
vector < int > vec[100001];
vector < int > :: iterator ii;
bool vizitat[100001];

int bfs(int nod)
{
    Q.push(nod);
    vizitat[nod] = true;
    while(!Q.empty())
    {
        x = Q.front();
        ii = vec[x].begin();
        while(ii != vec[x].end())
        {
            if(!vizitat[*ii])
                Q.push(*ii),vizitat[*ii] = true;
            ++ii;
        }
        Q.pop();
    }
}

int main()
{
    f >> n >> m;
    for(i = 1; i <= m; i++)
    {
        f >> x >> y;
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    for(i = 1 ; i <= n; i++)
        if(!vizitat[i])
            bfs(i),k++;
    g << k <<" ";
    return 0;
}