Cod sursa(job #1766009)

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

using namespace std;

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

int mat[1001][1001],x,poz,n,m,i,y,k;
queue < int > Q;
bool vizitat[100001];

int bfs(int nod)
{
    Q.push(nod);
    vizitat[nod] = true;
    while(!Q.empty())
    {
        x = Q.front();
        poz = mat[x][0];
        for(int i = 1; i <= poz; i++)
            if(!vizitat[mat[x][i]])
                Q.push(mat[x][i]),vizitat[mat[x][i]] = true;
        Q.pop();
    }
}

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