Cod sursa(job #1214573)

Utilizator cojocarugabiReality cojocarugabi Data 30 iulie 2014 20:14:21
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100000;
vector <int> a[nmax];
int s[nmax];
void dfs(int nod)
{
    s[nod]=1;
    for (int i=0;i<a[nod].size();++i)
        if (!s[a[nod][i]])
           dfs(a[nod][i]);
}
int main(void)
{
   ifstream fi("dfs.in");
   ofstream fo("dfs.out");
   int n,m;
   fi>>n>>m;
   for (int i=1;i<=m;++i)
   {
       int x,y;
       fi>>x>>y;
       a[x].push_back(y);
       a[y].push_back(x);
   }
   int N=0;
   for (int i=1;i<=n;++i)
       if (!s[i])
         {
            ++N;
            dfs(i);
         }
   fo<<N<<"\n";
}