Cod sursa(job #971284)

Utilizator StBogdanStoicescu Bogdan StBogdan Data 8 iulie 2013 21:01:11
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream IN("bfs.in");
ofstream OUT("bfs.out");
int i,n,m,lv[2500][2500];
bool sel[2500];
void citire()
{
    int x,y;
    IN>>n>>m;
    for(i=1;i<=m;i++)
    {
        IN>>x>>y;
        lv[x][0]++;lv[y][0]++;
        lv[x][lv[x][0]]=y;
        lv[y][lv[y][0]]=x;
    }
}

void dfs(int nod)
{
    int j;
    sel[nod]=true;
    for(j=1;j<=lv[nod][0];j++) if(!sel[lv[nod][j]]) dfs(lv[nod][j]);
}
int main()
{
   int nr=0;
  citire();
  memset(sel,false,sizeof(sel));
  for(i=1;i<=n;i++) if(!sel[i]) {nr++;dfs(i);}
  OUT<<nr;
}