Cod sursa(job #782755)

Utilizator PatrikStepan Patrik Patrik Data 29 august 2012 19:17:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
	#include<stdio.h>
	#include<vector>
	#define MAX 100001
	using namespace std;
	FILE *f , *g ;
	int n , m , comp , viz[MAX] ;
	vector<int> a[MAX];
	
	
	void citire();
	void dfs(int nod);
	void tipar();
	
	int main()
	{
		citire();
		for( int i = 1 ; i<= n ; ++i )
			if(!viz[i])
				dfs(i),comp++;
		tipar();
		return 0;
	}
	
	void citire()
	{
		f=fopen("dfs.in" , "r" );
		fscanf(f , "%d%d" , &n , &m );
		int x , y;
		for( int i = 1 ; i <= m ; ++i )
		{
			fscanf(f , "%d%d" , &x , &y ) ;
			a[x].push_back(y) ;
			a[y].push_back(x);
		}
		fclose(f);
	}
	
	void dfs(int i)
	{
		vector<int>::iterator it;
		viz[i] = 1;
		for(it = a[i].begin() ; it < a[i].end() ; ++it )
			if(!viz[*it])
				dfs(*it);
	}
	
	void tipar()
	{
		g=fopen("dfs.out" , "w" );
		fprintf(g , "%d" , comp );
		fclose(g);
	}