Cod sursa(job #1558282)

Utilizator GrandmasterSoucup Bogdan Grandmaster Data 28 decembrie 2015 23:04:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
#include <map>
#include <iomanip>
#include <time.h>
#include <stdio.h>
//#include <iostream>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
int x[100001];
void dfs(int val, vector<int> vec[100001])
{
    x[val] = 1;
    for(int i = 0; i < vec[val].size(); i++)
        if(x[vec[val][i]] == 0)
        {
            dfs(vec[val][i], vec);
        }
}
int main()
{
    int a, b, n, m, number = 0;
    vector<int> vec[100001];
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        vec[a - 1].push_back(b - 1);
        vec[b - 1].push_back(a - 1);
    }
    for(int i = 0; i < n; i++)
    {
        if(x[i] == 0)
            number++;
            dfs(i, vec);
    }
    cout << number;
    return 0;
}