Cod sursa(job #2370442)

Utilizator pinbuAdi Giri pinbu Data 6 martie 2019 12:11:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.57 kb
#include <bits/stdc++.h>
#define N 100001
using namespace std;

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

vector<int> v[N];
int t[N],n,m;

void dfs(int vf,int val)
{
    t[vf]=val;
    
    for(auto s:v[vf])
        if(t[s]==0)
            dfs(s,val);
}

int main()
{
    int i,a,b;
    
    fin>>n>>m;
    
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    int nr=0;
    
    for(i=1;i<=n;i++)
        if(t[i]==0)
        {
            nr++;
            dfs(i,nr);
        }
    fout<<nr;
    return 0;
}