Cod sursa(job #652918)

Utilizator BugirosRobert Bugiros Data 26 decembrie 2011 19:19:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 100005;

vector<int> vecin[MAXN];
bool vizitat[MAXN];
int n;

void citire()
{
    int m,a,b;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf ("%d%d",&n,&m);
    for (int i = 1;i <= m;++i)
    {
        scanf ("%d%d",&a,&b);
        vecin[a].push_back(b);
        vecin[b].push_back(a);
    }
}

void dfs(int nod)
{
    vizitat[nod] = true;
    for (unsigned int i = 0;i < vecin[nod].size();++i)
        if (!vizitat[vecin[nod][i]])
            dfs(vecin[nod][i]);
}

int main()
{
    int c_conex = 0;
    citire();
    for (int i = 1;i <= n;++i)
        if (!vizitat[i])
        {
            ++c_conex;
            dfs(i);
        }
    printf ("%d",c_conex);
    return 0;
}