Cod sursa(job #1191729)

Utilizator impulseBagu Alexandru impulse Data 28 mai 2014 16:32:44
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
//
//  main.cpp
//  dfs
//
//  Created by Alexandru Bâgu on 5/28/14.
//  Copyright (c) 2014 OkieDokie. All rights reserved.
//

#include <fstream>
#include <memory.h>

using namespace std;

#define NMax 51

struct vertex {
    int k;
    vertex* next;
    void make(int key) {
        k = key;
        next = NULL;
    }
    void add(int key) {
        vertex* base = this;
        while(base->next != NULL) base = base->next;
        base->next = new vertex;
        base->next->make(key);
    }
};
vertex V[NMax];
int T[NMax];

void dfs(int k)
{
    T[k] = 1;
    vertex* v = V + k;
    for(vertex* i = v->next; i; i = i->next)
        if(T[i->k] == 0)
            dfs(i->k);
}

int main(int argc, const char * argv[])
{
    ifstream input("dfs.in");
    int N, M;
    input>>N>>M;
    for(int i = 0; i <= N; i++)
        V[i].make(i);
    memset(T, 0, N);
    for(int i = 0; i < M; i++)
    {
        int x, y;
        input>>x>>y;
        V[x].add(y);
        V[y].add(x);
    }
    input.close();
    ofstream output("dfs.out");
    int conex = 0;
    for(int i = 1; i <= N; i++) {
        if(T[i] == 0) {
            dfs(i);
            conex ++;
        }
    }
    output<<conex;
    output.close();
    return 0;
}