Pagini recente » Cod sursa (job #3206233) | Cod sursa (job #1479649) | Cod sursa (job #337895) | Cod sursa (job #2858491) | Cod sursa (job #1191725)
//
// 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;
}