Cod sursa(job #2796960)

Utilizator vasiliumirunamariaVasiliu Miruna-Maria vasiliumirunamaria Data 9 noiembrie 2021 07:17:50
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define N 10005
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");


int nrc; //nr comp conexe
int viz[N];

class Graph {


public:
	int n; //nr de varfuri
	int m; //nr de muchii
	
	vector <int> a[N];

	Graph(int n, int m)
	{
		this->n = n;
		this->m = m;
	}
	void Citire_neorientat()
	{
		int i;
		int x, y;
		for (i = 1; i <= m; i++)
		{
			fin >> x >> y;
			a[x].push_back(y);
			a[y].push_back(x);
		}
	}
	void DFS(int x);
	/*void Citire_orientat()
	{
		int i;
		int x, y;
		
		for (i = 0; i < m; i++)
		{
			fin >> x >> y;
			a[x].push_back(y);

		}

	}


	void BFS(int x);
	*/
};

/*void Graph::BFS(int x)
{
	queue <int> q;
	int k, i;
	
	q.push(x);
	bool viz[N] = { 0 };
	int cost[N] = { 0 };
	viz[x] = 1;
	cost[x] = 0;
	while (!q.empty())
	{
		 k = q.front();
		 q.pop();
		for (i = 0; i < a[k].size(); i++)
			if (!viz[a[k][i]])
			{
				q.push(a[k][i]);
				viz[a[k][i]] = 1;
				cost[a[k][i]] = cost[k] + 1;
			}

		
	}

	for (i = 1; i <= n; i++)
		if (viz[i] == 0)
			cout << -1 << " ";
		else cout << cost[i] << " ";



}*/

void Graph::DFS(int x)
{
	int i;
	viz[x] = 1;
	for(i = 0; i < a[x].size(); i++)
		if (!viz[a[x][i]])
		{
			//viz[a[x][i]] = 1;
			DFS(a[x][i]);
		}
	
}

int main()
{
	int n, m;
	
	fin >> n >> m;
	Graph g(n, m);
	//g.Citire_orientat();
	//g.BFS(S);
	g.Citire_neorientat();
	for(int i = 1; i <= n; i++)
		if (!viz[i])
		{
			nrc++;
			g.DFS(i);
		}

	fout << nrc;





	return 0;
}