Cod sursa(job #1564533)

Utilizator alexarnautuArnautu Alexandru alexarnautu Data 9 ianuarie 2016 19:01:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <vector>
#include <cstdio>
#include <bitset>

using namespace std;

FILE * iFile;
FILE * oFile;

vector<int> vertices[100002];
bitset<100002> visited;
int nodes, edges, answer; 

void read()
{
	int source, destination;

	fscanf(iFile, "%d%d", &nodes, &edges);

	for(int i = 1; i <= edges; i++)
	{
		fscanf(iFile, "%d %d", &source, &destination);

		vertices[source].push_back(destination);
		vertices[destination].push_back(source);
	} 

}

void dfs(int start_node)
{
	int i;

	visited[start_node] = 1;
	
	for(i=0;i<vertices[start_node].size();i++)
	{
		if(visited[vertices[start_node][i]] == 0)
		{
			dfs(vertices[start_node][i]);
		}
		
	}
}

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

	read();

	for(int i=1;i<=nodes;i++)
	{
		if(visited[i] == 0)
		{
			answer++;
			dfs(i);
		}
	}

	fprintf(oFile, "%d", answer);

	return 0;
}