Cod sursa(job #1676960)

Utilizator xandruGuzun Alexandru xandru Data 6 aprilie 2016 11:35:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<bits/stdc++.h>

using namespace std;
int cnt,viz[100005],n,m;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
typedef struct nod{
	int info;
	nod* next;
}*lnod;
lnod g[100005];
void add(int x, lnod &y)
{
	lnod r=new nod;
	r->info=x;
	r->next=y;
	y=r;
}
void citire()
{
	int i,x,y;
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		add(x,g[y]);
		add(y,g[x]);
	}
}
void DFS(int nod)
{
	lnod p;
	viz[nod]=1;
	for(p=g[nod];p!=NULL;p=p->next)
	if(viz[p->info]==0)
	{
		DFS(p->info);
	}
}
int main()
{
	citire();
	int i;
	cnt=0;
	for(i=1;i<=n;i++)
	{
		if(viz[i]==0){
			cnt++;
			DFS(i);
		}
	}
	fout<<cnt;
	
	
	return 0;
}