Дистанционная подготовка: Не понимаю в чем ошибка
Не понимаю в чем ошибка
от Dima Svetov - Четверг 20 Февраль 2014, 22:40
1992. Космические путешествия
  #include <iostream>
#include <list>
#include <vector>
#include <cstring>
#include <math.h>
#include <fstream>
bool used[1000];
std::vector < std::vector < int > > vi;
int timex = 0;
void dfs(int v, int size, int del){
timex ++;
used[v] = true;
for (int i = 0 ; i < size; ++i){
if (!used[i]&&vi[v][i]!=0&&i!=del){
dfs(i,size,del);
}
}
}
int main(){
int N,x,y;
std::ifstream fx("input.txt");
fx >> N;
vi.resize(N);
for (int i = 0; i < N; ++i){
vi[i].resize(N);
}
for (int i = 0; i < N-1; ++i){
fx >> x >> y;
vi[x-1][y-1] = 1;
vi[y-1][x-1] = 1;
}
int k = 0;
for (int i = 0; i < N; ++i){
for (int j = 0; j < N; ++j){
if (!used[i]&&j!=i){
memset(used,false,sizeof(used));
dfs(j,N,i);
memset(used,false,sizeof(used));
if (timex < N-1){
k++;
timex = 0;
break;
}
timex = 0;
}
}
}
std::cout << k;
return 0;
}


каждый раз дфсим без учитывая что в удаленную вершну нельзя заходить, если получили после обхода
N-1 вершину значит это не важная планета
В чем ошибка данного алгоритма
Re: Не понимаю в чем ошибка
от Peter Cherepanov - Пятница 21 Февраль 2014, 10:07
  Не надо никуда ходить. На важную планету ведут 2 или более тоннелей.

Надо ввести номера концов тоннелей, отсортировать их и посчитать те, которые встречаются 2 и более раз. Всё решается с помощью malloc() и qsort() .
Re: Не понимаю в чем ошибка
от Никита Пушкин - Среда 14 Январь 2015, 22:40
  Сортировки тоже не нужны.