Cod sursa(job #2641898)

Utilizator MiclosMiclos Eduard Miclos Data 13 august 2020 00:21:40
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>

const int Nodes = 100005;
bool Visited[Nodes];
int count;


struct Node {
	int index;
	struct Node* next;
};

struct Node* N[Nodes];


void addAdjacentNode(Node*& header, int i) {
	Node* iterator = header;
	
	while (iterator->next != NULL)
		iterator = iterator->next;

	Node* added = new Node;

	added->index = i;
	added->next = NULL;
	iterator->next = added;

	return;
}

void DFS(int index) {
	if (Visited[index]) return;
	Visited[index] = true;

	Node* iterator = N[index];
	while (iterator->next != NULL) {
		iterator = iterator->next;
		DFS(iterator->index);
	}

	return;
}

int main() {
	std::ifstream fin("DFS.in");
	std::ofstream fout("DFS.out");

	int nodes{}, edges{}, i{};
	fin >> nodes >> edges;

	for (i = 1; i <= nodes; i++) {
		N[i] = new Node;
		N[i]->index = i;
		N[i]->next = NULL;
	}

	while (edges--) {
		int x{}, y{};
		fin >> x >> y;
		
		addAdjacentNode(N[x], y);
		addAdjacentNode(N[y], x);
	}


	for (i = 1; i <= nodes; i++) {
		if (!Visited[i]) {
			DFS(i);
			count++;
		}
	}

	fout << count << "\n";

	fin.close();
	fout.close();

	return 0;
}