Cod sursa(job #2254602)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 5 octombrie 2018 16:56:30
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>
#define Dim 100003
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int N,M,x,y,ans;
bool viz[Dim];
vector < int > Varf[10];
stack < int > Vecini;

void Citire()
{
    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
        f>>x>>y;
        Varf[x].push_back(y);
        Varf[y].push_back(x);
    }
}

void DFS()
{
    while(!Vecini.empty())
    {
        int nod_cur=Vecini.top();
        Vecini.pop();
        for(unsigned int i=0;i<Varf[nod_cur].size();i++)
        if(viz[Varf[nod_cur][i]]==0)
        {
            viz[Varf[nod_cur][i]]=1;
            Vecini.push(Varf[nod_cur][i]);
        }

    }
}

int main()
{
    Citire();
    for(int i=1;i<=N;i++)
    if(viz[i]==0)
    {
       ans++;
       viz[i]=1;
       Vecini.push(i);
       DFS();

    }
    g<<ans;
    return 0;
}