Cod sursa(job #1072351)

Utilizator dumytruKana Banana dumytru Data 4 ianuarie 2014 13:02:46
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

unsigned n,m,sol=0;
vector<vector<unsigned> > graf;
vector<unsigned> is_visited;

void DFS_Visit(unsigned start_node)
{
    is_visited[start_node]=1;
    unsigned i,len=graf[start_node].size();
    for(i=0;i<len;i++)
    {
        if(is_visited[graf[start_node][i]]==0)
            DFS_Visit(graf[start_node][i]);
    }

}

void DFS()
{
    unsigned i;
    for(i=1;i<=n;i++)
    {
        if(is_visited[i]==0)
        {
             DFS_Visit(i);
             sol++;
        }
    }
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%u %u",&n,&m);
    unsigned i,u,v;
    graf.resize(n+1);is_visited.resize(n+1);
    for(i=1;i<=m;i++)
    {
        scanf("%u %u",&u,&v);
        graf[u].push_back(v);
        graf[v].push_back(u);
    }
    sol=0;
    DFS();
    printf("%u",sol);
    return 0;
}