Cod sursa(job #2391473)

Utilizator Costy_Suruniuc Constantin Costy_ Data 28 martie 2019 21:28:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
using namespace std;

void addEdge(vector<int> adj[], int u, int v)
{
	adj[u].push_back(v);
	adj[v].push_back(u);
}

int main()
{
	ifstream inFile;
	inFile.open("dfs.in");
	int N, M;
	inFile >> N >> M;
	vector<int> *lst = new vector<int>[N+1];
	int *viz = new int[N + 1];
	for (size_t i = 1; i <= N; ++i)
	{
		viz[i] = 0;
	}
	int count = 0;
	pair<int, int> edge;
	for (int i = 0; i < M; ++i)
	{
		inFile >> edge.first >> edge.second;
		addEdge(lst, edge.first, edge.second);

	}
	inFile.close();
	stack<int> stiva;
	for (size_t i = 1; i <= N; ++i)
	{
		if (viz[i] != 0) continue;
		count++;
		stiva.push(i);
		viz[i] = 1;
		while (stiva.empty() == false)
		{
			int temp = stiva.top();
			stiva.pop();
			for (auto it : lst[temp])
			{
				if (viz[it] != 0) continue;
				viz[it] = 1;
				stiva.push(it);
			}
		}
	}
	ofstream outFile;
	outFile.open("dfs.out");
	outFile << count;
	outFile.close();
}