~~~ c++
#include
#include
#include

#define TRUE 1
#define FALSE 0
#define MAX_POINT_NUM 103 /* 100 + 2 + 1 /
short int visited[MAX_POINT_NUM];
typedef struct Point PointPointer;
struct Point{
int name;
int x;
int y;
};

typedef struct adj_list* adj_listPointer;
struct adj_list{
int data;
adj_listPointer link;
};

adj_listPointer* adj_header_list = (adj_listPointer*)malloc(MAX_POINT_NUM * sizeof(adj_listPointer));

PointPointer* Stone_list = (PointPointer*)malloc(MAX_POINT_NUM * sizeof(PointPointer));

double jump;
int N;
int num=0, cnt=0;

double dist(int i, int n){
int distx = (Stone_list[i])->x - (Stone_list[n])->x;
int disty = (Stone_list[i])->y - (Stone_list[n])->y;
/*
printf("i.x:%d, i.y:%d, num.x:%d, num.y:%d, distx:%d, disty:%d\n",(Stone_list[i])->x, (Stone_list[i])->y, (Stone_list[n])->x, (Stone_list[n])->y, distx, disty);
*/
double dist = (double)(distx * distx + disty * disty);
dist = sqrt(dist);
return dist;
}

void Add_adj(int head, int tail){
adj_listPointer x;
adj_listPointer temp = (adj_listPointer)malloc(sizeof(adj_list));
temp->data = tail;
temp->link = 0;
if(!(adj_header_list[head])){
adj_header_list[head] = temp;
return;
}
x = adj_header_list[head];
while(x->link!=0){
x = x->link;
}
x->link=temp; return;
}
void Find(){
int i=0;
while(i double d = dist(i, num);
//printf("i=%d num=%d d=%lf\n", i, num, d);
if(jump >= d){/* add to adjacency list */
Add_adj(i, num);
Add_adj(num, i);
}
i++;
}
}

void dfs(int v){/* depth first search of a graph beginning at v */
adj_listPointer w;
visited[v] = TRUE;
cnt++;
for(w = adj_header_list[v]; w; w = w->link){
if(!visited[w->data])
dfs(w->data);
}
}

void Init(){
cnt=0;
num=0;
for(int i=0; i Stone_list[i] = 0;
adj_header_list[i] = 0;
}
}
void Add_to_Stone_list(){
int posx, posy;
scanf("%d", &posx);
scanf("%d", &posy);
PointPointer temp = (Point*)malloc(sizeof(Point));
temp->x = posx;
temp->y = posy;
temp->name=num;
Stone_list[num] = temp;
}

void Task(){
Add_to_Stone_list();
Find();
num++;
}
void FREE(){
for(int i=0; i if(Stone_list[i]){
free(Stone_list[i]);
}
if(adj_header_list[i]){
adj_listPointer p, temp;
p = adj_header_list[i];
while(p){
temp = p->link;
free(p);
p = temp;
}
}
}
}
int main(){
int cases;
scanf("%d", &cases);
while(cases--){
Init();
int jump_int=0;
scanf("%d", &jump_int);
jump = (double)jump_int;
/* starting Point /
Task();
/ end Point */
Task();
/*number of stone /
scanf("%d", &N);
while(N--){
Task();
}
dfs(0); / make DFS(0) spanning Tree */
//printf("cnt: %d\n", cnt);
//printf("num: %d\n", num);
if(cnt == num){
printf("YES\n");
}
else{
printf("NO\n");
}
FREE();
}
free(Stone_list);
free(adj_header_list);
}
~~~

BRAVEDUCK문제 알고리즘에 대한 질문인데요. 제가 짠 알고리즘은 먼저 출발점과 도착점을 포함, 모든 돌들의 좌표를 번호를 매겨 1차원 어레이에 차곡차곡 쌓으면서 각 입력을 받을때마다 기존에 받았던 좌표들과 비교하여 거리가 주어진 점프가능거리보다 작은 거리에 있는 좌표들을 adjacency list에 추가하도록 만들었습니다. 그래서 입력을 다 받고 나면 거리가 점프거리보다 가까운 점들끼리는 edge가 존재하도록 graph가 만들어지게 됩니다. 그 다음에 만약 이 그래프가 모두 connected되어있다면 오리가 점프해서 출발점에서 마지막까지 갈수 있다는 이야기가 되니까, DFS(0) spannig tree를 만드는 알고리즘을 돌려서 dfs가 한번 작동할떄마다 카운트수를 한개 씩 늘렷습니다. 마지막으로 DFS(0) spanning tree의 점 개수와 주어진 전체 점 개수가 일치한다면 모두다 연결되있는 그래프인 것이고 일치하지 않는다면 중간에 끊어져있는 그래프인 것이라는 사실을 이용해 YES, NO를 판별하였습니다.

이 알고리즘이 틀리다는 반례가 될만한 예제나 틀린 이유를 알고 싶습니다.

(그리고 , 추가로 메모리관리를 수동으로 하는 코딩은 되도록 지양하는 것이 좋다고 자주하는실수 모음에 써져있는데요. 그럼 c++로 코딩할떄도 메모리수동관리를 하지 않는게 좋은가요?)