Cod sursa(job #727869)

Utilizator pbobitzaPirvanescu Livius pbobitza Data 28 martie 2012 12:30:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<fstream>
#include<iostream>
#include<vector>

using namespace std;

typedef vector<int> L;

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

L v[100005];
vector <bool> viz(100005,false);
int n,m,nr=0;

void citeste()
{int x,y;
    in>>n;
    in>>m;
    for (int i=1;i<=m;++i)
     {
         in>>x;
         in>>y;
          v[x].push_back(y);
          v[y].push_back(x);
     }

}

void df(int nod)
{
    viz[nod]=true;
    for (int i=0;i<v[nod].size();++i)
     {
         if (viz[v[nod][i]]==false) df(v[nod][i]);
     }



}

int main()
{
    citeste();
    for (int j=1;j<=n;++j)
      if (viz[j]==false) {df(j);nr++;}

    out<<nr;
    return 0;
}