Cod sursa(job #598148)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 24 iunie 2011 17:35:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <vector>
#include <string.h>

#define max_n 100001
#define pb push_back

using namespace std;

int n,m,i;
vector <int> g[max_n];
vector <int>::iterator it;
bool ok[max_n];
int nrc,x,y;

ifstream in("dfs.in");
ofstream out("dfs.out");

void DF(int x) {
    vector <int>::iterator it;
    ok[x]=true;
    for (it=g[x].begin(); it!=g[x].end(); it++)
       if (!ok[*it]) DF(*it);

}

int main()
{
    in >> n >> m;
    for (i=1; i<=m; i++) {
       in >> x >> y;
       g[x].pb(y);
       g[y].pb(x);
       }
    memset(ok,false,sizeof(ok));

    nrc=0;
    for (i=1; i<=n; i++) {
        if (!ok[i]) {
            nrc++;
            DF(i);
        }
    }
    out << nrc << '\n';
    in.close();
    out.close();
    return 0;
}