Cod sursa(job #1818731)

Utilizator DoubleNyNinicu Cristian DoubleNy Data 29 noiembrie 2016 19:19:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
    #include <bits/stdc++.h>
    #include <vector>
    using namespace std;
     
    vector <int> ans[100003];
    int n,m,cnt;
    int visited[100003];
     
    void Dfs(int node){
		visited[node] = 1;
		for(int i = 0; i < ans[node].size(); i++)
			if(!visited[ans[node][i]])
				Dfs(ans[node][i]);
    }
    int main() {
		ifstream cin("dfs.in");
		ofstream cout("dfs.out");
		cin >> n >> m;
        for(int i=0; i<m; i++){
             int a,b;
             cin >> a >> b;
             ans[a].push_back(b);
             ans[b].push_back(a);
        }
        for(int i=1; i<=n; i++){
                 if(!visited[i]){
                      cnt++;
                      Dfs(i);
                 }
        }
        cout << cnt;
    	return 0;
    }