pascal 33706번 오름차순 최단 경로 (백준)

var n,m,a,b,i:int64;v:array[1..200000]of byte;
begin
readln(n,m);
for i:=2 to n do v[i]:=0;v[1]:=1;
for i:=1 to m do begin
readln(a,b);
if a>b then v[a]:=1 else v[b]:=1;
end;
for i:=2 to n do if v[i]=0 then begin v[1]:=0;break;end;
if v[1]=0 then write('NO')else write('YES');
end.

풀이 : 그래프

 

https://www.acmicpc.net/problem/33706

주어진 그래프의 모든 정점이 연결되어 있고, 중복된 간선이 주어지지 않음이 보장된다.

 

 

만약 1-2-4-3 이라는 그래프가 있다면 위의 조건을 만족하지 않습니다. (1에서 3으로 가는 것보다 1에서 4로 갈때의 가중치가 반드시 작기 때문입니다)

 

문제에선 양방향 그래프라 주어졌지만,

위의 조건들을 만족하는 그래프는 정점i -> 정점 j (단 i<j) 인 단방향 그래프이며 1번에서 모든 정점으로 이동이 가능한 그래프 입니다. 

 

반드시 모든 정점이 연결된 상태의 무방향 그래프로 주어진다고 문제에 나와있기 때문에

ex)

6 3

1 2

3 4

5 6

이런 경우들은(무방향으로 바라보았을때, 모든 정점이 연결되지 않음) 입력으로 주어지지 않습니다.

 

즉 간선을 (a,b) 이런식으로 입력받으면 둘 중 더 큰 수의 node를 방문했다고 처리한 다음, 방문하지 못한 node가 있는지를 확인하면 됩니다. (당연히 1번에서 시작하므로 1번 node는 방문했다고 처리합니다)

 

ex)

4 4
1 3
4 1
3 2
2 4

1->3 (3번 노드 방문)

1->4 (4번 노드 방문)

2->3 (3번 노드 방문)

2->4 (4번 노드 방문)

 

즉 2번 노드는 갈 수 없으므로 위의 조건을 만족하지 못하는 그래프 임을 알아낼수 있습니다.