Cod sursa(job #1461866)

Utilizator TeodorescuStefanEduardTeodorescu Stefan Eduard TeodorescuStefanEduard Data 16 iulie 2015 15:50:52
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

#define nmax 100005
#define mmax 200005

int n,m,s[nmax],start[nmax]={},t[2][mmax];

void df(int);

int main()
{
	fstream in("dfs.in", ios::in);
	fstream out("dfs.out", ios::out);

	int k=0,i,j,sum=0;

	in>>n>>m;

	while(in>>i>>j)
	{
		k++;
		t[0][k]= j;
		t[1][k]= start[i];
		start[i]=k;
		k++;
		t[0][k]= i;
		t[1][k]= start[j];
		start[j]=k;
	}

	for(i=1;i<=n;i++)
		if(s[i] == 0)
		{
			df(i);
			sum++;
		}
	
	out<<sum;



        
    in.close();
    out.close();

	return 0;
}

void df(int nod)
{

	int k;
	s[nod]= 1;
	k= start[nod];

	while(k)
	{
		if(s[k] == 0)
			df(k);
		k= t[1][k];
	}

}