Cod sursa(job #1166761)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 3 aprilie 2014 20:02:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
 vector <int> v[100005];
 int n,m,sol,top,st[100005],use[100005];

 void DFS()
 { int i,j,x;

    for(i=1;i<=n;i++)
     if (!use[i])
      { sol++;
         top=1; st[top]=i;
          while(top)
           { x=st[top]; top--;

              for(j=0;j<v[x].size();j++)
               if (!use[v[x][j]])
                { top++;
                  st[top]=v[x][j];
                  use[v[x][j]]=1; }
           }
      }
 }

int main()
{ int i,x,y;
   f>>n>>m;

    for(i=1;i<=m;i++)
     { f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
     }

   DFS();

   g<<sol<<"\n";
    return 0;
}