Description
UVa 599 - The Forrest for the Trees
Problem: Given a forest you are to write a program that counts the number of trees and acorns
Sample Input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
(A,B)
(B,C)
(B,D)
(D,E)
(E,F)
(B,G)
(G,H)
(G,I)
(J,K)
(K,L)
(K,M)
****
A,B,C,D,E,F,G,H,I,J,K,L,M,N
(A,B)
(A,C)
(C,F)
**
A,B,C,D,F
Sample Output
1
2
3
4
There are 2 tree(s) and 1 acorn(s).
There are 1 tree(s) and 1 acorn(s).
Ideas
Use union find algorithm to find acorns. To find acrons find vertices such that parent(v) = v and parent(u)!=v for all vertices other than v.
Acrons have no incomming or outgoing edges.
Total number of connected components in acyclic graph = V - E
Trees = (V - E) - acrons
Solution
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
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
vector<int> edge_count(26, 0);
int v = 0, e = 0, acorns = 0;
string s, vertices;
while (cin >> s)
{
if (s[0] == '*')
break;
edge_count[s[1] - 'A']++;
edge_count[s[3] - 'A']++;
e++;
}
cin >> vertices;
for (auto c : vertices)
{
if (c != ',')
{
if (edge_count[c - 'A'] == 0)
acorns++;
v++;
}
}
printf("There are %d tree(s) and %d acorn(s).\n", v - e - acorns, acorns);
}
return 0;
}