11503 – Virtual Friends UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2498

Union Find disjoint sets.

How I did it

• I read the number of cases.
• For each case I read the number of friendships to read.
• For each name I check if the name exist in a map. If a name is not in the map I added to the map.
• I call union_set.
• Print the size of the set with the name of one person in the new friendship.

Hints

•  For each friendship you need to print one line with the size of the set. i.e (3 4 print ans, 3 4 print ans again).
• The answer is just union find.

Code

#include <iostream>
#include <cstdio>
#include <map>
#define  ELEMENTS  100002

using namespace std;

map<string,int> myMap;
int index;

int parent[ELEMENTS];
int rank[ELEMENTS];
int numDisjointSets;

void make_sets(int number_of_elements)
{
    numDisjointSets = number_of_elements;
    int i;
    for(i = 0; i < number_of_elements; i++)
    {
        parent[i] = i;
        rank[i] = 1;
    }
}

int find_set(int element)
{
    if(element != parent[element])
        parent[element] = find_set(parent[element]);
    return parent[element];
}

bool isSameSet(int i, int j)
{
    return find_set(i) == find_set(j);
}

void set_union(int x, int y)//where x and y are elements of different sets
{
    int rx, ry; //roots or representatives of x and y sets
    rx = find_set(x);
    ry = find_set(y);
    if(rx == ry) // it means the elements already are in the same set
        return;

    numDisjointSets--;
    if(rank[rx] > rank[ry])
    {
        rank[rx] += rank[ry];
        parent[ry] = rx;
    }
    else
    {
        rank[ry] += rank[rx];
        parent[rx] = ry;
    }
}

int getNumSets()
{
    return numDisjointSets;
}

int sizeOfSet(int i)
{
    return rank[find_set(i)];
}

void setIndex(string str)
{
    if(myMap.find(str) == myMap.end())
       myMap[str] = index++;
}

int main()
{
    string name1, name2;
    int casos, friendship;

    scanf("%d", &casos);
    while(casos--)
    {
        index = 0;
        scanf("%d", &friendship);
        make_sets(ELEMENTS);
        myMap.clear();

        for(int x=0; x<friendship; x++)
        {
            cin>>name1>>name2;
            setIndex(name1);
            setIndex(name2);

            set_union(myMap[name1], myMap[name2]);

            int answer = sizeOfSet(myMap[name1]);
            printf("%d\n", answer);
        }
    }
return 0;
}

10684 – The jackpot UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1625

Dynamic Programming, 1D range sum, Kanade Algorithm.

How I did it

• I read the data in a vector.
• Init ans = tot = 0. Ans will save the answer, tot will save the cumulative value of the range.
• Traverse the vector. If I found a negative cumulative value set tot = 0. Otherwise increment the range.
• If ans is less than 0 print losing streak, otherwise I print ans.

Hints

•  It is a clasic DP problem. Standard Kanade Algorithm.
• 0 is a valid answer.

Code

#include <cstdio>
#include <algorithm>

using namespace std;

int vec[10010];

int main()
{
    int ele, ans, tot;

    while(scanf("%d", &ele))
    {
        if(!ele)
           break;

        for(int x=0; x<ele; x++)
            scanf("%d", &vec[x]);

        ans = tot = 0;

        for(int x=0; x<ele; x++)
        {
            tot += vec[x];
            ans = max(tot, ans);

            if(tot < 0)
              tot = 0;
        }

        if(ans > 0)
           printf("The maximum winning streak is %d.\n", ans);
        else
            printf("Losing streak.\n");
    }
return 0;
}

247 – Calling Circles UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=183

Graphs, Strongly Connected Components.

How I did it

• I read the number of nodes and edges.
• Read the data of the graph.
• I parse the strings and set a map<string,int> with the indices of the nodes(0 to nodes – 1).
• I save the graph as an Adjacency list.
• Traverse all nodes and for each unvisited node call Tarjan Algorithm.
• En every tarjan call I find the nodes that belong to the current SCC, and print the elements in that subset (map<string,int>).

Hints

•  The key is parse the strings and assign a name for each person.
• The input is really small.
• I print a blank line between the cases.(The last case does not need the blank line).

Code

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#define  DFS_BLACK 1
#define  DFS_WHITE -1

using namespace std;
typedef vector<int> vi;

vector<vi> graph;
vi dfs_num, dfs_low, S, visited;
int dfsNumberCounter, numSCC;
set<string> mySet;
map<string,int> myMap;
map<int, string> nameMap;

void init(int nodes)
{
    graph.clear();
    graph.resize(nodes);
    dfs_num.resize(nodes);
    fill(dfs_num.begin(), dfs_num.end(), DFS_WHITE);
    dfs_low.resize(nodes);
    fill(dfs_low.begin(), dfs_low.end(), 0);
    visited.resize(nodes);
    fill(visited.begin(), visited.end(), 0);
}

void readGraph(int edges)
{
    myMap.clear();
    mySet.clear();
    int index = 0;

    string str1, str2;
    int node1, node2;

    for(int x=0; x<edges; x++)
    {
        cin>> str1 >> str2;

        if(mySet.find(str1) == mySet.end())
        {
            myMap[str1] = index;
            nameMap[index] = str1;
            mySet.insert(str1);
            index++;
        }
        if(mySet.find(str2) == mySet.end())
        {
            myMap[str2] = index;
            nameMap[index] = str2;
            mySet.insert(str2);
            index++;
        }
        node1 = myMap[str1];
        node2 = myMap[str2];
        graph[node1].push_back(node2);
    }
}

void tarjanSCC(int node)
{
    dfs_low[node] = dfs_num[node] = dfsNumberCounter++;
    S.push_back(node);
    visited[node] = 1;

    for(int x=0; x<graph[node].size(); x++)
    {
        if(dfs_num[graph[node][x]] == DFS_WHITE)
          tarjanSCC(graph[node][x]);
        if(visited[graph[node][x]])
            dfs_low[node] = min(dfs_low[node], dfs_low[graph[node][x]]);
    }

    if(dfs_low[node] == dfs_num[node])//This is the root
    {
        ++numSCC;
        while(1)
        {
            int v = S.back();
            S.pop_back();

            visited[v] = 0;

            if(node == v)
            {
                printf("%s\n", nameMap[v].c_str());
                break;
            }
            else
                printf("%s, ", nameMap[v].c_str());
        }
    }
}

int main()
{
    string str;
    int nodes, edges, casos = 1;
    bool flag = false;
    while(scanf("%d %d", &nodes, &edges))
    {
        if(!nodes && !edges)
           break;

        init(nodes);
        readGraph(edges);

        dfsNumberCounter = numSCC = 0;
        if(!flag)
           flag = true;
        else
            printf("\n");
        printf("Calling circles for data set %d:\n", casos++);
        for(int i=0; i<graph.size(); i++)
        {
            if(dfs_num[i] == DFS_WHITE)
               tarjanSCC(i);
        }
    }
return 0;
}