Cod sursa(job #1783913)

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

#define NMAX 100000
using namespace std;

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

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

void add(int index, int val){
    if(g[index]==NULL){
        g[index] = new nod;
        g[index]->x = val;
        g[index]->next = NULL;
    }
    else{
        nod* ptr = g[index];
        while(ptr->next!=NULL)ptr = ptr->next;
        ptr->next = new nod;
        ptr = ptr->next;
        ptr->x = val;
        ptr->next = NULL;
    }
}

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<n;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;
}