Cod sursa(job #2228218)

Utilizator BloodRainBurceanu Gabriel BloodRain Data 2 august 2018 22:53:41
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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;

void dfs(int start) 
{
	stack<int> s;
	s.push(start);
	vis[start] = true;
	while (!s.empty())
	{
		int crt = s.top();
		s.pop();
		for (Node* node = v[crt]; node != nullptr; node = node->next)
			if (!vis[node->val])
			{
				s.push(node->val);
				vis[node->val] = true;
			}
			

	}
}

int main()
{
	ifstream in("dfs.in");
	ofstream out("dfs.out");

	

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

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

	for (int i = 0; i < m; ++i)
	{
		int u, w;
		in >> u >> w;
		--u; --w;
		if (v[u] != nullptr)
		{
			v[u]->next = new Node( w );
		}
		else 
		{
			v[u] = new Node( w );
		}
	}

	int comp = 0;
	for (int i = 0; i < n; ++i)
	{
		if (vis[i])
			continue;
		comp++;
		dfs(i);
	}

	out << comp << "\n";

	return 0;
}