Cod sursa(job #3030301)

Utilizator BadHero112Ursu Vasile BadHero112 Data 17 martie 2023 16:41:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>
using ll=long long;
#define S second
#define F first
#define endl '\n'
#define spid ios_base::sync_with_stdio(false);cin.tie(NULL);
const int mod=1e9+7;
const double pi=3.14159265359;
const int maxn=200001;
using namespace std;

int n,m,chk[maxn];
vector<vector<int>> A(maxn,vector<int>());

void dfs(int i){
	chk[i]=1;
	for(int j=0;j<A[i].size();j++){
		if(chk[A[i][j]]==0)dfs(A[i][j]);
	}
}

int main(){
	ifstream cin("dfs.in");
	ofstream cout("dfs.out");
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int c1,c2;
		cin>>c1>>c2;
		c1--;
		c2--;
		A[c1].push_back(c2);
		A[c2].push_back(c1);
	}
	int cnt=0;
	for(int i=0;i<n;i++){
		if(!chk[i]){
			cnt++;
			dfs(i);
		}
	}
	cout<<cnt<<endl;
}