Nu aveti permisiuni pentru a descarca fisierul grader_test3.in

Cod sursa(job #3149078)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 6 septembrie 2023 10:23:45
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
 
#define fisier 1
 
using namespace std;
 
typedef long long ll;
 
const int mod = 1000000007;
const double dancila = 3.14159265359; // PI 
const double eps = 1e-9;
 
int n, m;
vector<vector<int> > v;
int cc;
bool viz[200002];
void dfs(int nod)
{
	viz[nod] = 1;
	for(int i = 0; i < v[nod].size(); ++i)
	{
		int vecin = v[nod][i];
		if(!viz[vecin])
			dfs(vecin);
	}
}
int main()
{
	#ifdef fisier
		ifstream cin("dfs.in");
		ofstream cout("dfs.out");
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;
	v.resize(n+1);
	
	for(int i = 1; i <= m; ++i)
	{
		int a, b;
		cin >> a >> b;
		v[a].pb(b);
		v[b].pb(a);	
	}
	for(int i = 1; i <= n; ++i)
		if(!viz[i])
		{
			++cc;
			dfs(i);
		}
	cout << cc;
	return 0;
}