Cod sursa(job #728825)

Utilizator Dragan_ValentinDragan Valentin Dragan_Valentin Data 28 martie 2012 23:57:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;


vector <bool> selected;
vector <vector<int> > a(100010);
/*typedef vector<int> lista_adj;
lista_adj a[100010];
*/

void DFS(int node)
{
    selected[node]=true;
    for (int i=0; i<a[node].size(); i++)
        if (selected[a[node][i]]==false) DFS(a[node][i]);
}




int main()
{
	int n,m,x,y,i;
	ifstream f("dfs.in");
	f>>n>>m;
	selected.reserve(n+1);
	//a.reserve(n+30);
	for (i=0; i<m; i++) {
		f>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
    f.close();
	
	/*for (i=1; i<=n; i++) {
		cout<<i<<"---";
		for (int j=0; j<a[i].size(); j++)
			cout<<a[i][j]<<' ';
		cout<<'\n';
	}*/
	
    int nr=0;
    for (i=0; i<=n; i++)
		selected[i]=false;
	
	for (i=1; i<=n; i++)
        if (selected[i]==false) {
            ++nr;
            DFS(i);
        }
    
	freopen("dfs.out","w",stdout);
	printf("%d\n",nr);
    return 0;
}