Cod sursa(job #2075928)

Utilizator adystar00Bunea Andrei adystar00 Data 25 noiembrie 2017 21:06:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int vc[100001];
vector<int> g[100001];
void dfs(int node)
{
    int a,j;
    vc[node]=1;
    a=g[node].size();
    for(j=0;j<a;j++)
        if(vc[g[node][j]]==0)
            dfs(g[node][j]);
}
int main()
{
    ifstream fin ("dfs.in");
    ofstream fout ("dfs.out");
    int n,i,a,b,nrsol=0,m;
    fin>>n>>m;
    for(i=1;i<=m;i++)
        {
            fin>>a>>b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
    for(i=1;i<=n;i++)
    {
        if(vc[i]==0){
            dfs(i);
            nrsol++;
        }
    }
    fout<<nrsol;
    return 0;
}