Cod sursa(job #2797496)

Utilizator IoanaLiviaPopescu15Ioana Livia IoanaLiviaPopescu15 Data 9 noiembrie 2021 23:57:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define N 100001

using namespace std;

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

bool visited[N];

class Graph {
public:

	vector <int> adiacenta[N];
    void addEdge(int h, int t);
	void DFS(int vf);

};

void Graph::addEdge(int h,int t)
{
     adiacenta[h].push_back(t);
     adiacenta[t].push_back(h);
}

void Graph::DFS(int vf)
{
	visited[vf] = true;
	for(int i = 0; i < adiacenta[vf].size(); ++i)
		if (!visited[adiacenta[vf][i]])
			DFS(adiacenta[vf][i]);
}


int main()

{

	int n, m, n1, n2, conexe = 0;
	fin >> n >> m;

	Graph g;
    for (int i = 1; i <= m; i++)
    {
        fin >> n1 >> n2;
        g.addEdge(n1,n2);
    }


	for(int i = 1; i <= n; i++){
        if (!visited[i])
        {
           conexe += 1;
           g.DFS(i);
        }
	}

	fout << conexe;
	return 0;

}