Cod sursa(job #1783923)

Utilizator martonsSoos Marton martons Data 19 octombrie 2016 16:42:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdio>
#include <deque>

#define NMAX 100005
using namespace std;

struct nod{
    int x;
    nod* next;
};

nod* g[NMAX];
bool vis[NMAX];
int n, m;

void add(int index, int val){
    nod* nod_nou = new nod;
    nod_nou->x=val;
    nod_nou->next = g[index];
    g[index] = nod_nou;
}

void dfs(int s){
    deque<int> nodes;
    nodes.push_back(s);
    vis[s] = true;

    while(!nodes.empty()){
        int crt = nodes.front();
        vis[crt] = true;
        nodes.pop_front();
        for(nod* ptr = g[crt]; ptr!=NULL;ptr=ptr->next){
            if(!vis[ptr->x])nodes.push_back(ptr->x);
        }
    }
}

int main()
{
    FILE* f=fopen("dfs.in", "r");

    fscanf(f, "%d %d", &n, &m);
    for(int i=0;i<m;i++){
        int x, y;
        fscanf(f, "%d %d", &x, &y);
        add(x, y);
        add(y, x);
    }

    fclose(f);

    int comp=0;

    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i);
            comp++;
        }
    }

    f=fopen("dfs.out", "w");
    fprintf(f, "%d", comp);
    return 0;
}