Cod sursa(job #1400550)

Utilizator theprdvtheprdv theprdv Data 25 martie 2015 12:24:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

fstream fin("dfs.in", ios::in);
fstream fout("dfs.out", ios::out);
#define MAXN 100005
vector <int> list[MAXN];
bool used[MAXN];
int n, m;

void read()
{
    int x, y;
    fin >> n >> m;
    for(int i=1; i<=m; i++)
        fin >> x >> y,
        list[x].push_back(y),
        list[y].push_back(x);
}
void DFS(int node)
{
    used[node] = true;
    for(int i=0, size = list[node].size(); i<size; i++)
    if(!used[list[node][i]])
        DFS(list[node][i]);
}

int main()
{
    int comp = 0;
	read();
    for(int i=1; i<=n; i++)
        if(!used[i])
            comp++,
            DFS(i);
    fout << comp;

    fin.close();
	fout.close();
	return 0;
}