Cod sursa(job #2228216)

Utilizator BloodRainBurceanu Gabriel BloodRain Data 2 august 2018 22:44:47
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 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(200000, nullptr);
static vector<bool> vis(200000, false);

void dfs(int start) 
{
	stack<int> s;
	s.push(start);
	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);
			

	}
}

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

	

	int n, m;
	in >> n >> m;
	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 < m; ++i)
	{
		if (vis[i])
			continue;
		comp++;
		dfs(i);
	}

	out << comp << "\n";

	return 0;
}