Cod sursa(job #1191725)

Utilizator impulseBagu Alexandru impulse Data 28 mai 2014 16:15:05
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 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 100001

struct vertex {
    int Key;
    vertex* Next;
    void make(int key) {
        Key = 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(vertex* v)
{
    if(T[v->Key] == 0) {
        T[v->Key] = 1;
        v = v->Next;
        while(v != NULL) {
            dfs(v);
            v = v->Next;
        }
    }
}

int main(int argc, const char * argv[])
{
    ifstream input("dfs.in");
    int N, M;
    input>>N>>M;
    for(int i = 1; i <= N; i++)
        V[i].make(i);
    memset(T + 1, 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) {
            conex ++;
            dfs(V+i);
        }
    }
    output<<conex;
    output.close();
    return 0;
}