Cod sursa(job #749280)

Utilizator geniucosOncescu Costin geniucos Data 16 mai 2012 15:50:38
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream>
#include<vector>
using namespace std;
int val,nr,p,u,x1,y11,n,m,i,d[100010],x[100010];
vector < int > h[100010];
vector < int >::iterator it;
int main()
{
ifstream f("dfs.in");
ofstream g("dfs.out");
//freopen("dfs.in","r",stdin);	
//freopen("dfs.out","w",stdout);
//scanf("%d",&n);
//scanf("%d",&m);
f>>n>>m;
for(i=1;i<=m;i++)
{
	//scanf("%d",&x1);
	//scanf("%d",&y1);
	f>>x1>>y11;
	h[x1].push_back(y11);
	h[y11].push_back(x1);
}
for(i=1;i<=n;i++)
if(d[i]==0)
{
	d[i]=1;
	x[1]=i;
	p=1;
	u=1;
	nr++;
	while(p<=u)
	{
		for(it=h[x[p]].begin();it!=h[x[p]].end();it++)
		{
			val=*it;
			if(d[*it]==0)
			{
				u++;
				x[u]=*it;
				d[*it]=1;
			}
		}
		p++;
	}
}
//printf("%d\n",nr);
g<<n<<'\n';
return 0;
}