Cod sursa(job #1504478)

Utilizator IasmiIasmina Iasmi Data 17 octombrie 2015 19:43:56
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

const int Nmax=100005;
vector <int> G[Nmax];
queue <int> Q;
int N,M;
int Use[Nmax];
void read()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int x,y;
        fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x); // in lista de adiacenta a lui y il punem pe x

    }


}
void dfs(int Nod)
{
    Use[Nod]=1;
    for(int i=0;i<(int)G[Nod].size();i++)
    {
        int vecin=G[Nod][i];
        if(Use[vecin]==0)
            dfs(vecin);
    }
}
int main()
{
    read();
    int nr_insule=0;
    for(int i=1;i<=N;i++)
    {
        if(!Use[i])
            {
                dfs(i);
                nr_insule++;
            }

    }

    cout<<nr_insule;
    return 0;
}