This is an easy problem from uva judge https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4027
- I read the number of cases.
- Read the string.
- I traverse the string and I trace the current node with a stack. If the current element is in the top of the stack I pop that element otherwise I put the edge in the graph. After that I put the current element in the stack.
- For the answer I traverse my map and print the key a value size.
- Accepted!
Hints
- I’m building the graph using map<char, set<char> > graph.
- I trace the node to build the graph using a stack.
Code
/* *Author: Fabian Calsina *Date: 4/7/2016 */ #include <iostream> #include <cstdio> #include <stack> #include <map> #include <set> using namespace std; map<char, set<char> > graph; stack<char> currentNode; void cleanData() { while(currentNode.size()) currentNode.pop(); graph.clear(); } int main() { string str; int casos; char tmp; scanf("%d", &casos); for(int i=1; i<=casos; i++) { cin>>str; for(int x=0; x<str.size(); x++) { if(x-1 < 0) { currentNode.push(str[x]); continue; } if(currentNode.top() == str[x]) currentNode.pop(); else { tmp = currentNode.top(); graph[tmp].insert(str[x]); graph[str[x]].insert(tmp); currentNode.push(str[x]); } } printf("Case %d\n", i); for(map<char, set<char> >::iterator iter = graph.begin(); iter != graph.end(); iter++) { printf("%c = %d\n", iter->first, iter->second.size()); } cleanData(); } return 0; }