Cod sursa(job #1760765)

Utilizator Mihaibv13Mihai Stoian Mihaibv13 Data 21 septembrie 2016 10:51:41
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector <int>lv[100000];
vector <int>::iterator ii;
queue <int> corn;
int n,m;
bool used[100000];
int nodnou()
{

for(int i=1;i<=n;i++)

{
    if (used[i]==false) return i;
}
return false;



}
int main()
{
    FILE *f=fopen("dfs.in","r");

    int x,y;
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        lv[x].push_back(y);
        lv[y].push_back(x);


    }
    int ok=0;

        while(1)
         {
             x=nodnou();
             if(x==false)break;
               while(!corn.empty())
             {
                 corn.pop();
             }
             ok++;
             corn.push(x);
             used[x]=true;


   while(!corn.empty())
   {
       x=corn.front();
       corn.pop();
       for(ii=lv[x].begin();ii<lv[x].end();++ii)
       if(used[*ii]==false)
       {
           used[*ii]=true;
           corn.push(*ii);
       }




   }



         }
 FILE *g=fopen("dfs.out","w");
fprintf(g,"%d",ok);



    return 0;
}