Cod sursa(job #1905508)

Utilizator roxi22Roxi C. roxi22 Data 6 martie 2017 08:43:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <bits/stdc++.h>

using namespace std;

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

#define nmax 100001

int nrComp,n,m,x,y;
vector<int> ad[nmax];

int viz[nmax];

void DFS(int nodStart)
{
    viz[nodStart]=1;
    for(int i=0;i<ad[nodStart].size();i++)
        if(viz[ad[nodStart][i]]==0)
            DFS(ad[nodStart][i]);
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        {fin>>x>>y;
        ad[x].push_back(y);
        ad[y].push_back(x);}
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
            {nrComp++;
            DFS(i);}
    fout<<nrComp;
    fin.close();
    fout.close();
    return 0;
}