Cod sursa(job #793514)

Utilizator unsilviuContvechidontdeactivatepls unsilviu Data 3 octombrie 2012 13:53:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <vector>
using namespace std;

vector <int> v[100001];
int vz[100001];
int nr,n,m;

void dfs(int x) {
    int it;
    vz[x]=1;
    for (it=0; it<v[x].size(); ++it)
        if (!vz[v[x][it]])
            dfs(v[x][it]);

}

int main() {
    int i,a,b;
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    f>>n>>m;
    for (i=1; i<=m; i++) {
        f>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (i=1; i<=n; i++) {
        if (v[i].size()&&!vz[i]) {
            nr++;
            dfs(i);
        }
        if (!v[i].size())
            nr++;
    }

    g<<nr<<'\n';
    g.close();
    return 0;

}