Cod sursa(job #1508586)

Utilizator IliescuDanAndreiIliescu Dan Andrei IliescuDanAndrei Data 22 octombrie 2015 18:47:56
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 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;
  //out << current <<" ";
  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<=n; i++)
    if(!visited[i]) 
    {
      dfs(i);
      //out<<"\n";
      compcon++;
    }

  out<<compcon;
  return 0;
}