Cod sursa(job #1540032)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 1 decembrie 2015 23:22:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100001;


void dfs(vector<int>g[], int x, int mark[]) {

	mark[x] = 1;

	for(unsigned i = 0 ; i < g[x].size() ; ++i)
		if(mark[ g[x][i] ] == 0)
			dfs(g, g[x][i] , mark);
}


int main() {

	vector<int> g[NMAX];

	int mark[NMAX]; int cnt = 0;
	
	memset(mark, NMAX, 0);

	int n; int m;

	fin >> n >> m;

	for(int i = 1; i <= m; ++i) {

		int x; int y;
		fin >> x >> y;

		g[x].push_back(y);
		g[y].push_back(x);

	}

	for(int i = 1; i <= n ; ++i)
		if(mark[i] == 0)
			dfs(g, i, mark), ++cnt;

	fout << cnt << '\n'; 

	return 0;
}