Cod sursa(job #1001884)

Utilizator lukkerLiNoimi Semain lukker Data 26 septembrie 2013 14:55:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 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()) {
			cout<<q.front()<<" ";
			for(int k=0;k<(int)p[q.front()].v.size();k++) {
				//cout<<"|"<<p[q.front()].v[k]<<" ";
				if(!p[p[q.front()].v[k]].m) q.push(p[q.front()].v[k]);
			}
			p[q.front()].m = true;
			q.pop();
		}
		//cout<<endl;
	}
	
	fout<<c<<endl;
	return 0;
}