Cod sursa(job #2079339)

Utilizator serban24Popovici Serban-Florin serban24 Data 1 decembrie 2017 01:03:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
#include <bits/stdc++.h>

using namespace std;

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

vector <int> A[200005];
int viz[100005];

void DFS(int x){
	int i;

	for(i=0;i<A[x].size();i++)
		if(!viz[A[x][i]]){
			viz[A[x][i]]=viz[x];
			DFS(A[x][i]);
		}
}

int main(){
	int n,m,i,x,k=0,y;

	fin>>n>>m;

	for(i=1;i<=m;i++){
		fin>>x>>y;
		A[x].push_back(y);
		A[y].push_back(x);
	}

	for(i=1;i<=n;i++){
		if(!viz[i]){
			k++;
			viz[i]=k;
			DFS(i);
		}
	}

	fout<<k;

    return 0;
}