Cod sursa(job #2386516)

Utilizator raduandreicaRadu Andreica raduandreica Data 23 martie 2019 10:37:26
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in"); ofstream fout("dfs.out");
vector <vector<int>>g(100010);
void citire(int n)
{
    for(int i=0 ; i<n ; i++)
    {
        int a, b;
        fin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
}
int f[100010] = {0};
vector<int> dfs(int a , vector<int> v)
{
    f[a] = 1;
    for(int i=0 ; i<g[a].size() ; i++)
    {
        if(!f[g[a][i]])
        {
            f[g[a][i]] = 1;
            v.push_back(g[a][i]);
            v = dfs(g[a][i], v);
        }
    }
    return v;
}
int main()
{
    int n , m , ans = 0;
    fin>>n>>m;
    citire(m);
    vector <int> ff(n+1,0);
    for(int i=1 ; i<=n ; i++)
    {
        vector<int> a;
        if(ff[i]==0)
        {
            ff[i] = 1;
            a = dfs(i, a);
            for(int j=1 ; j<=n ; j++)
                f[j] = 0;
            while (!a.empty())
            {
                int r = a.back();
                a.pop_back();
                ff[r] = 1;
            }
            ans++;
        }
    }
    fout<<ans;
}