Cod sursa(job #3249423)

Utilizator PrizlopanIustinPrizlopan Iustin George PrizlopanIustin Data 16 octombrie 2024 11:08:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <queue>
#include <list>
#include <fstream>
#include <unordered_set>
#include <cstring>
#include <stdio.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
struct nod
{
	int cost = -1;
	list <int> p;
}el[100005];
bool frecventa[100005];
void crearelista(nod el[], int n, int m, bool ordonat)
{
	int x1, x2;
	for (int i = 1; i <= m; i++)
	{
		in >> x1 >> x2;
		el[x1].p.push_back(x2);
		if (ordonat == 0)
			el[x2].p.push_back(x1);
	}
}
void afisarelista(nod el[], int n)
{
	for (int i = 1; i <= n; i++)
	{
		out << "Nodul " << i << " duce la urmatoarele noduri:" << '\n';
		for (auto p = el[i].p.begin(); p != el[i].p.end(); p++)
			out << *p << ' ';
		out << '\n';
	}
}
void clear(queue <int>& q1)
{
	std::queue<int> emp;
	swap(q1, emp);


};
void DFS(nod el[], queue <int> q1)
{
	while (!q1.empty())
	{
		auto i = q1.front();
		q1.pop();
		if (frecventa[i] == 0)
		{
			frecventa[i] = 1;
			for (auto t = el[i].p.begin(); t != el[i].p.end(); t++)
				q1.push(*t);
		}
	};
}
void DFS2(nod el[], int curr)
{
	frecventa[curr] = 1;
	for (auto t = el[curr].p.begin(); t != el[curr].p.end(); t++)
	{
		if (frecventa[*t] == 0)
			DFS2(el, *t);
	}
}

int main()
{
	int n, m, s, px;
	in >> n >> m;
	crearelista(el, n, m, 0);
	queue <int> q1;
	int cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		if (frecventa[i] == 0)
		{
			cnt++;
			//q1.push(i);
			DFS2(el, i);
		}
	}
	out << cnt;
}