Cod sursa(job #509766)

Utilizator DanceKrissCristian Oancea DanceKriss Data 11 decembrie 2010 18:20:57
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <iostream>
#include<stdio.h>

using namespace std;

int a[1000][1000],v[1000];
long n,m;

void citire()
{
    freopen("dfs.in","r",stdin);
   cin>>n>>m;

    int i,j,x,y;
    for(i=1;i<=m;i++)
      cin>>x>>y,a[x][y]=1,a[y][x]=1;

}

void dfs(int i)
{
    int j;
    v[i]=1 ;
    for(j=1;j<=n;j++)
     if(a[i][j] && !v[j]) dfs(j);

}

int solve()
{
    int i,c=0;

    for(i=1;i<=n;i++)
      if(!v[i]) {c++; dfs(i);}

         return c;

}


int main()
{
   freopen("dfs.out","w",stdout);
    citire();
    printf("%d\n",solve());

    return 0;
}