Cod sursa(job #1188653)

Utilizator 0051David Sera 0051 Data 20 mai 2014 09:31:24
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

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

#define MAX 100000

vector < int > G[MAX];

bool viz[MAX];

int n,m,x,y;

void dfs(int nod)
{
    if(viz[nod]==0)
    {
        viz[nod]=1;
        for(int i=0;i<G[nod].size();i++)
            dfs(G[nod][i]);
    }
}

int main()
{
    fin>>n>>m;
    int i;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    x=0;
    for(i=1;i<=n;i++)
        if(viz[i]==0){
            dfs(i);
            x++;
        }
    fout<<x<<endl;
    fin.close();
    fout.close();
    return 0;
}