Cod sursa(job #671475)

Utilizator OanaCristinaFlorescu Oana Cristina OanaCristina Data 31 ianuarie 2012 16:03:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");

int n,m,S[100001],cc;
struct nod
{
	int inf;
	nod* next;
};

nod* LA[100001];

void add(int x, int y)
{
	nod* n=new nod;
	n->inf=y;
	n->next=LA[x];
	LA[x]=n;
	n=new nod;
	n->inf=x;
	n->next=LA[y];
	LA[y]=n;
}

void citire()
{
	in>>n>>m;
	int i,x,y;
	for(i=1;i<=m;i++)
	{
		in>>x>>y;
		add(x,y);
	}
}

void dfs(int x)
{
	nod* nc=LA[x];
	while(nc)
	{
		int vecin=nc->inf;
		if(S[vecin]==0)
		{
			S[vecin]=cc;
			dfs(vecin);
		}
		nc=nc->next;
	}
}

int main()
{
	citire();
	for(int i=1;i<=n;i++)
		if(!S[i])
		{
			cc++;
			dfs(i);
		}
	out<<cc;
	return 0;
}