Cod sursa(job #715326)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 17 martie 2012 00:21:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
                                                     
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

long N[100001] = {0};
//vector<int> M[100000];
vector<int> *M;

int main(void)
{
 fstream fin("dfs.in",ios::in);
 fstream fout("dfs.out",ios::out);
 long Noduri,Muchii,i,a,b,Co,k;
 M = new vector<int>[100001];
 pair<int,int> *c;
 fin >> Noduri >> Muchii;
 for (i = 0;i < Muchii;i += 1)
  {
   fin >> a >> b;
   M[a].push_back(b);
   M[b].push_back(a);
  }

 Co = 0; 
 for (k = 1;k <= Noduri;k += 1)
  {
   if (N[k] <= 0)
     {
      Co += 1;
      queue<pair<int,int> *> q;
      q.push(new pair<int,int>(k,Co));
      N[k] = Co;
      while (q.empty() == 0)
       {
        c = q.front();
        q.pop();
        for (i = 0;i < M[c->first].size();i += 1)
         {
          if (N[M[c->first].at(i)] <= 0)
            {
             q.push(new pair<int,int>(M[c->first].at(i),Co));
             N[M[c->first].at(i)] = Co;
            }
         }
       }
     }
  }
 fout << Co;
 fin.close();
 fout.close();
 return 0;
}