차원의 나무 여행
문제
정점의 개수가 N, 간선의 개수가 N-1인 트리가 주어진다.
간선으로 직접 연결되지 않은 정점으로 이동하는 것을 워프라고 한다.
각 정점을 최대 한 번만 방문할 수 있을 때, 가능한 워프의 최대 횟수를 구하여라.
시작 정점은 임의로 고를 수 있으며, 시작 정점을 고르는 것도 워프이다.
입력
첫 번째 줄에 N이 주어진다. 두 번째 줄부터 N-1개의 줄에 걸쳐 간선의 정보가 주어진다.
간선은 u, v의 형태로 주어진다.
이는 트리의 u번 정점과 v번 정점이 간선으로 연결되어 있음을 의미한다.
출력
첫 번째 줄에 가능한 워프의 최대 횟수를 출력한다.
제한
2<=N<=500 1<=u, v<=N
예제 입력 1
3
1 2
2 3
예제 출력 1
2
풀이
처음에는 이게 무슨 문제일까 싶었는데 천천히 생각을 해보니까
트리에서 워프가 불가능한 경우가 거의 없음을 알게 되었다.
이렇게 트리가 한 점에 모두 이어진 경우에만 정점의 개수 - 1번 워프를 할 수 있다.
다른 경우에는 정점의 개수만큼 워프가 가능하다.
풀 때 확신은 없었는데 애드 훅 문제는 AC를 받았으면 정답임을 증명하는 거니까..
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
using namespace std;
int v[101];
int n, m;
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long k;
long long a, b, c, d;
string s;
cin >> n;
vector<vector<int>> graph(n+1);
for(int i=0;i<n-1;i++){
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
int count=0;
vector<int> check(n+1, 0);
int save = 0;
int ma=0;
for(int i=1;i<=n;i++){
if(ma < graph[i].size()){
ma = graph[i].size();
save = i;
}
}
if(graph[save].size()==n-1){
cout << n-1;
}
else cout << n;
return 0;
}