Solution UVA: 599 - The Forrest for the Trees

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss599 - The Forrest for the Trees	Accepted	C++11	0.260	0.000	1342	4 mins ago

Problem: http://uva.onlinejudge.org/external/5/599.pdf

Summary: Given a forest you are to write a program that counts the number of trees and acorns

Suggest:
- Because the input is "forest" and the problem defines it as a graph consisting of "trees" with no cycles, we can calculate using the formula tree = v - e - a, where v is the number of vertices, e is the number of edges, and a is the number of isolated vertices (You can try some simple cases and derive the formula)

#include<bits/stdc++.h>

using namespace std;

int t;

string s;

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> t;

    while(t--){

       

        int v= 0, e= 0, a= 0;

        unordered_map<char, bool> tree;

       

        while(cin >> s && s[0]!='*'){

       

            tree[s[1]] = true;

            tree[s[3]] = true;

            e++;

        }

       

        cin >> s;

        for(auto c:s)

            if (c!=','){

                v++;

                if (!tree[c]) a++;

            }

           

        cout<<"There are "<<v-e-a<<" tree(s) and "<<a<<" acorn(s).\n";

    }

}