Cod sursa(job #2217804)

Utilizator Mihaibv13Mihai Stoian Mihaibv13 Data 2 iulie 2018 11:49:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 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;
}