Cod sursa(job #750934)

Utilizator andrey13Letcanu Andrei andrey13 Data 23 mai 2012 17:39:48
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<cstdio>
#define pb push_back
#include<vector>

using namespace std;

int n,m,x,y,i;
bool sel[100000];
vector<int> v[100000];

bool oO(){
   int i;
   for(i=1;i<=n;i++)if(sel[i]==false)return true;
   return false;}

void df(int x){
  int i;
   sel[x] = true;
   for(i=0; i<v[x].size(); i++)
      if(!sel[v[x][i]])
        df(v[x][i]);
}

int main(){
  freopen("dfs.in","r",stdin);
  freopen("dfs.out","w",stdout);
  scanf("%d %d",&n,&m);
  for(i=1;i<=m;i++){
    scanf("%d %d",&x,&y);
    v[x].pb(y);
    v[y].pb(x);}
int k=0;
while(oO())
    for(i=1;i<=n;i++)if(!sel[i]){
    df(i);
    k++;}
    printf("%d",k);
  return 0;
}