Cod sursa(job #2024645)

Utilizator newbabBabin Claudiu newbab Data 20 septembrie 2017 22:46:07
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
vector < vector <int> > graph;
vector <int> rnd;
vector <int> vz;
void DFS(int node)
{
    vz[node]=1;
    for (int i=1;i<graph[node].size();i++)
    {
        if (vz[graph[node][i]]==0)
        {
            DFS(graph[node][i]);
        }
    }
}

int main()
{
    ifstream input;
    input.open("bfs.in");
    ofstream output;
    int n,m;
    int tot=0;
    input>>n>>m;
    int x,y;
    rnd.pb(0);
    for (int i=0;i<=n;i++)
    {
        graph.pb(rnd);
        vz.pb(0);
    }
    for (int i=0;i<m;i++)
    {
        cin>>x>>y;
        graph[x].pb(y);
        graph[y].pb(x);
    }
    for (int i=1;i<=n;i++)
    {
        if (vz[i]==0){tot++;DFS(i);}
    }
    input.close();
    output.open("bfs.out");
    output<<tot;
    output.close();

}