Cod sursa(job #2007254)

Utilizator epermesterNagy Edward epermester Data 2 august 2017 12:59:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#include<stack>
#include<vector>
using namespace std;

struct csucsok {
	vector<int> szomszedok;
	bool visited = false;
};

int main() {
	ifstream in("dfs.in");
	int N, M;
	in >> N >> M;
	csucsok* csucs = new csucsok[N];
	for (;M;--M) {
		int honnan, hova;
		in >> honnan >> hova;
		csucs[honnan - 1].szomszedok.push_back(hova - 1);
		csucs[hova - 1].szomszedok.push_back(honnan - 1);
	}
	stack<int> s;
	int result = 0;
	for (int i = 0; i < N; ++i)
		if (!csucs[i].visited) {
			s.push(i);
			while (!s.empty()) {
				int jelenlegi = s.top();
				s.pop();
				for (vector<int>::iterator it = csucs[jelenlegi].szomszedok.begin(); it != csucs[jelenlegi].szomszedok.end(); it++)
					if (!csucs[*it].visited) {
						s.push(*it);
						csucs[*it].visited = true;
					}
			}
			result++;
		}
	ofstream out("dfs.out");
	out << result;
}