Cod sursa(job #897233)

Utilizator Gabriela19091993Busca Gabriela Gabriela19091993 Data 27 februarie 2013 19:29:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<iostream>
#include<vector>
#include<fstream>
using namespace std;

int v[100001];
vector <int> vec[100001];

void df(int a)
{
     v[a]=1;
     for(int i=0;i<vec[a].size();i++)
             if(v[vec[a][i]]==0)
                     df(vec[a][i]);
     }

int main()
{
   
    int n,m,i,a,b;
    int nr=0;
    ifstream in("dfs.in");
    ofstream out("dfs.out");
    in>>n;
    in>>m;
    for(i=1;i<=m;i++)
    {
        in>>a>>b;
        vec[a].push_back(b);
        vec[b].push_back(a);
        }
    for(i=1;i<=n;i++)
        v[i]=0;
    for(i=1;i<=n;i++)
        if(v[i]==0)
        {
           nr++;
           df(i);
           }
    out<<nr;
    return 0;
   
}