Cod sursa(job #1001880)

Utilizator lukkerLiNoimi Semain lukker Data 26 septembrie 2013 14:42:42
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

struct nod {
	bool m; 
	vector<int> v;
	void add(int x) {
		v.push_back(x);
	};
};

int main() {
	ifstream f("dfs.in");
	ofstream fout("dfs.out");
	int n, m;
	int c = 0;
	nod p[100001];
	f>>n>>m;
	for(int i=1;i<=n;i++) p[i].m = false;
	for(int i=1;i<=m;i++) {
		int x,y;
		f>>x>>y;
		p[x].add(y);
		p[y].add(x);
	}
	for(int i=1;i<=n;i++) {
		if(p[i].m) continue;
		c++;
		queue<int> q;
		q.push(i);
		while(!q.empty()) {
			for(int k=0;k<(int)p[i].v.size();k++) {
				if(!p[p[i].v[k]].m) q.push(p[i].v[k]);
			}
			p[q.front()].m = true;
			q.pop();
		}
	}
	
	fout<<c<<endl;
	return 0;
}