Cod sursa(job #935893)

Utilizator Mihai20Mihai20 Mihai20 Data 5 aprilie 2013 00:53:54
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <vector>

#define NMAX 100000
using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");


vector <int> muchie[NMAX];
int n,m,co;
bool b[NMAX];

void citire(){
	int i,x,y;
	in>>n>>m;
	for(i=1;i<=m;i++)
		{
		in>>x>>y;
		muchie[x].push_back(y);
		muchie[y].push_back(x);
	}
}

void DFS(int y)
{
    int j,x;
    b[y]=true;
    for(j=0;j<muchie[y].size();j++)
    {
        x=muchie[y][j];
        if(b[x]==false)
        {
            b[x]=true;
            DFS(x);
        }
    }
}

void componente(){
	int i;
	for(i=1;i<=n;++i){
		if(b[i]==false){
			co++;
			DFS(i);
		}
	}
}

int main(){
	citire();
	componente();
	out<<co;
	return 0;
}