Cod sursa(job #2780598)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 7 octombrie 2021 12:52:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
ifstream f("dfs.in");
ofstream g("dfs.out");

class Graph_Solver
{
	int n, m;
	vector<int> v[100002];
	bool visited[100002];
	public:
		void dfs(int nod)
		{
			visited[nod] = 1;
			for(auto x : v[nod])
				if(!visited[x])
					dfs(x);
		}
		void citire()
		{
			f >> n >> m;
			for(int i = 1; i <= m; ++i)
			{
				int a, b;
				f >> a >> b;
				v[a].push_back(b);
				v[b].push_back(a);
			}
		}
		int conex()
		{
			int ans = 0;
			for(int i = 1; i <= n; ++i)
				if(!visited[i])	
					dfs(i), ++ans;
			return ans;
		}
};

Graph_Solver gr;
int main()
{
	gr.citire();
	g << gr.conex() << '\n';
	return 0;
}