Cod sursa(job #2095869)

Utilizator novistaAlex Staicu novista Data 28 decembrie 2017 12:47:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define DIM 100005
using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
int n,m,v[DIM],con;
vector <int> l[DIM];
queue <int> q;
int main()
{
    int i,j,h,x;
    fin>>n>>m;
    for (h=1;h<=m;h++)
    {
        fin>>i>>j;
        l[i].push_back(j);
        l[j].push_back(i);
    }
    for (i=1;i<=n;i++)
    {
        if (v[i]==0)
        {
            con++;
            v[i]=1;
            q.push(i);
            while (!q.empty())
            {
                x=q.front();
                for (j=0;j<l[x].size();j++)
                    if (v[l[x][j]]==0)
                    {
                        v[l[x][j]]=1;
                        q.push(l[x][j]);
                    }
                q.pop();
            }
        }
    }
    fout<<con;
    fin.close();
    fout.close();
    return 0;
}