Cod sursa(job #1889959)

Utilizator Mihaibv13Mihai Stoian Mihaibv13 Data 22 februarie 2017 22:35:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
vector <int> lv[100000];
vector <int>::iterator it;
int viz[100000];
int main()
{ int i,n,m;
    FILE *f=fopen("dfs.in","r");
    FILE *g=fopen("dfs.out","w");
    fscanf(f,"%d%d",&n,&m);
  for(i=1;i<=m;i++)
  { int to,from;
  fscanf(f,"%d%d",&from,&to);
   lv[from].push_back(to);
   lv[to].push_back(from);

  }
  int j,comp=0,nc;
  queue <int> corn;
  for(j=1;j<=n;j++)
  {
    if(viz[j]==0)
    {
       comp++;
       corn.push(j);
       while(!corn.empty())
       {
        nc=corn.front();
        corn.pop();
        for(it=lv[nc].begin();it!=lv[nc].end();++it)
        {
          if(viz[*it]==0)
          {
             viz[*it]=1;
             corn.push(*it);

          }
        }

       }


    }




  }
  fprintf(g,"%d",comp);
    return 0;
}