Cod sursa(job #710786)

Utilizator hunter_ionutzzzFarcas Ionut hunter_ionutzzz Data 10 martie 2012 19:12:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct nod{int val;
        nod *next;
};
nod *v[100001],*q;
bool frecv[100001];
int i,a,n,b,m,nr;
inline void bf(int x)
{nod *q = v[x];
	if (q)
		while (q)
		{   if (!frecv[q->val])
			{   frecv[q->val] = true;
			    bf(q->val);
			}
			q = q -> next;
		}
}
int main()
{   fin >> n >> m;
    for (i=1;i<=m;++i)
	{   fin >> a >> b;
	    q = new nod;
		q -> next = v[a];
		q -> val = b;
		v[a] = q;
		q = new nod;
		q -> next = v[b];
		q -> val = a;
		v[b] = q;
	}
	for (i=1;i<=n;++i)
		if (!frecv[i])
		{   frecv[i] = true;
			++nr;
		    bf(i);
		}
	fout << nr;
	return 0;
}