Cod sursa(job #856364)

Utilizator oancea_horatiuOancea Horatiu oancea_horatiu Data 16 ianuarie 2013 13:05:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ofstream o("dfs.out");
ifstream d("dfs.in");
int i,j,m,n,x,y,a[100002],k;
int main()
  {
    vector<int> v[100001];
    stack<int> q;
    vector<int>::iterator it;
    d>>n>>m;
    for (i=1;i<=m;i++) {d>>x>>y; v[x].push_back(y); v[y].push_back(x);};
    k=0;
    for (i=1;i<=n;i++)
    {
      if (a[i]==0)
      {
        k++;
        q.push(i);
        while (!q.empty())
        {
          x=q.top();
          q.pop();
          for (it=v[x].begin();it!=v[x].end();++it) if (a[*it]==0) {q.push(*it); a[*it]=k;};
        };
      };
    };
    o<<k;
  }