Cod sursa(job #1004576)

Utilizator contulmeuMunteanu Vasile contulmeu Data 3 octombrie 2013 08:53:23
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <iostream>
#include<vector>

using namespace std;
const int MAXN=100001;
vector <int> G[MAXN];
//vector <int> Nc(Max Size, init value);
vector <int> Nc[MAXN];
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int a[100][100],used[MAXN];
   int componente_conexene=0;

void dfs(int nod)
{
   used[nod]=1;
  // cout<<nod<<endl;
   Nc[componente_conexene].push_back(nod);
   for(int i=0;i<G[nod].size();i++)
   {
       int new_nod=G[nod][i];
      if(!used[new_nod])
       dfs(new_nod);
   }
}
int main()
{
   int n;
   fin>>n >> m;
   int x,y;
   while(fin>>x>>y)
   {
      G[x].push_back(y);
      G[y].push_back(x);
   }


   for(int i=1;i<=n;i++)
   {
   if(!used[i])
   {
    dfs(i);componente_conexene++;}
   }
   fout<<componente_conexene;


   return 0;
}