Cod sursa(job #1107806)

Utilizator oancea_horatiuOancea Horatiu oancea_horatiu Data 14 februarie 2014 12:19:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <vector>
using namespace std;

vector <pair<int,int> > g[100005];
int m,n;
bool check[100005]={0};

void read()
{
  ifstream d("dfs.in");
  d>>n>>m;
  int x,y;
  for (int i=1;i<=m;i++)
  {
    d>>x>>y;
    g[x].push_back(make_pair(x,y));
    g[y].push_back(make_pair(y,x));
  }
}

void dfs(int v)
{
  check[v]=1;
  vector <pair<int,int> >::iterator iv;
  for (iv=g[v].begin(); iv!=g[v].end(); iv++)
  {
    if (!check[(*iv).second]) dfs((*iv).second);
  }
}

int getNrCompCon()
{
  int k=0;
  for (int i=1;i<=n;i++)
  {
    if (!check[i])
    {
      dfs(i);
      k++;
    }
  }
  return k;
}

void write()
{
  ofstream o("dfs.out");
  o<<getNrCompCon();
}

int main()
{
  read();
  write();
}