Cod sursa(job #1044624)

Utilizator rvnzphrvnzph rvnzph Data 30 noiembrie 2013 09:49:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <stdio.h>
#include <iostream>
#include <cstring>

using namespace std;

struct graf
{
	int node;
	graf *link;

	graf(int node,graf *link)
	{
		this->node=node;
		this->link=link;
	}
}*g[100001];

int use[100001];

void add(graf *&g,int y)
{
	graf *p=new graf(y,g);
	g=p;
}

void dfs(int at)
{
	use[at]=1;
	while(g[at])
	{
		if(!use[g[at]->node]) dfs(g[at]->node);
		g[at]=g[at]->link;
	}
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);

	int N,M,x,y;

	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;++i)
	{
		scanf("%d%d",&x,&y);
		add(g[x],y);
		add(g[y],x);
	}

	memset(use,0,sizeof(use));
	int cnt=0;

	for(int i=1;i<=N;++i)
		if(!use[i]) ++cnt, dfs(i);

	printf("%d\n",cnt);

	return 0;
}