Cod sursa(job #1508574)

Utilizator IliescuDanAndreiIliescu Dan Andrei IliescuDanAndrei Data 22 octombrie 2015 18:37:49
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<fstream>
#include<vector>

using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");

int n, m, compcon; 
bool visited[100001];
vector <int> vertex[100001];

void dfs(int current)
{
  int next, i;
  visited[current] = true;

  for(i=0; i<vertex[current].size(); i++)
  {
    next = vertex[current][i];
    if(!visited[next])
      dfs(next);
  }
}

int main()
{
  int i, x, y;
  in>>n>>m;
  for(i=1; i<=m; i++)
  {
    in>>x>>y;
    vertex[x].push_back(y);
    vertex[y].push_back(x);
  }
  
  for(i=1; i<=m; i++)
    if(visited[i]) dfs(i);
    else compcon++;

  out<<compcon;
  return 0;
}