Pagini recente » Cod sursa (job #2275494) | Cod sursa (job #1805425) | Cod sursa (job #294700) | Cod sursa (job #1527792) | Cod sursa (job #1191729)
//
// 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;
}