Cod sursa(job #2456478)

Utilizator Alex_dudeDudescu Alexandru Alex_dude Data 14 septembrie 2019 14:25:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#define _CRT_SECURE_NO_WARNINGS
#define ALEX_THE_DUDE

#define M_MAX 200000
#include <stdio.h>
#include <vector>
using namespace std;

FILE *fin, *fout;
int n, m;

vector<vector<int>> v;
bool viz[M_MAX];

void read()
{
	int i;
	fscanf(fin, "%d %d", &n, &m);

	for (i = 0; i <= n; i++)
	{
		v.push_back(vector<int>());
	}

	int f, s;
	for (i = 0; i < m; i++)
	{
		fscanf(fin, "%d %d", &f, &s);

		v[f].push_back(s);
		v[s].push_back(f);
	}
}

void dfs(int node)
{
	if (!viz[node])
	{
		viz[node] = true;
		int index;
		
		for (index = 0; index < v[node].size(); index++)
		{
			dfs(v[node][index]);
		}
	}
}

int cnt = 0;

void solve()
{
	int node;

	for (node = 1; node <= n; node++)
	{
		if (!viz[node])
		{
			dfs(node);
			cnt++;
		}
	}
}

void print()
{
	fprintf(fout, "%d", cnt);
}

int main()
{
	fin = fopen("dfs.in", "r");
	fout = fopen("dfs.out", "w");

	read();
	solve();
	print();

	return 0;
}