12582 – Wedding of Sultan UVA Solution

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;
}