Cod sursa(job #2228233)

Utilizator BloodRainBurceanu Gabriel BloodRain Data 2 august 2018 23:34:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

struct Node
{
	int val;
	Node* next;

	Node( int val) 
	{
		this->val = val;
		next = nullptr;
	}
};

static vector<Node*> v; 
static vector<bool> vis;


static ifstream in("dfs.in");
static ofstream out("dfs.out");

static bool test = false;
void dfs(int start) 
{
	vis[start] = true;

	if (test)
		out << start << " ";
	
	if (v[start] == nullptr)
		return;

	stack<int> s;
	s.push(start);
	

	while (!s.empty())
	{
		int crt = s.top();

		Node* node;
		for (node = v[crt]; node != nullptr; node = node->next)
			if (!vis[node->val])
			{
				if (test)
					out << node->val << " ";
				s.push(node->val);
				vis[node->val] = true;
				break;
			}

		if (node == nullptr)
			s.pop();		
	}
}

int main()
{
	

	int n, m;
	in >> n >> m;

	v.resize(n + 1, nullptr);
	vis.resize(n + 1, false);

	for (int i = 0; i < m; ++i)
	{
		int u, w;
		in >> u >> w;
		if (u > w)
		{
			int aux = w;
			w = u;
			w = aux;
		}

		

		Node* node = new Node(w);
		node->next = v[u];
		v[u] = node;

		node = new Node(u);
		node->next = v[w];
		v[w] = node;
		
	}

	int comp = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (vis[i])
			continue;
		comp++;
		dfs(i);
		if (test)
			out << "\n----------------\n";
	}

	out << comp << "\n";

	return 0;
}