Cod sursa(job #1804156)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 12 noiembrie 2016 11:53:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define  MaxN 100005
using namespace std;
 
FILE *IN,*OUT;
int N,M,Comp=0,X,Y;
bool visited[MaxN];
vector <int> Graph[MaxN];
void DFS(int node)
{
	visited[node]=true;
	for(int i=0;i<Graph[node].size();i++)
	{
		if(!visited[Graph[node][i]])
			DFS(Graph[node][i]);
	}
}
int main()
{
    IN=fopen("dfs.in","r");
    OUT=fopen("dfs.out","w");

	fscanf(IN,"%d%d",&N,&M);
	for(int i=1;i<=M;i++)
	{
		fscanf(IN,"%d%d",&X,&Y);
		Graph[X].push_back(Y);
		Graph[Y].push_back(X);
	}
	for(int i=1;i<=N;i++)
		if(!visited[i])DFS(i),Comp++;
	fprintf(OUT,"%d",Comp);

	return 0;
}