UVA 10583 Solution

#include<cstdio>
using namespace std;

int parent[50001];

int findparent(int n)
{
    return parent[n]==n? n: findparent(parent[n]);
}

int main()
{
    int n,m,tc=1,a,b;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        if (m+n==0) return 0;
        for (int i=1;i<=n;i++) parent[i]=i;
        while (m--)
        {
            scanf("%d%d",&a,&b);
            parent[findparent(a)]=findparent(b);
        }
        int r=0;
        for (int i=1;i<=n;i++)
            if (parent[i]==i) r++;
       
        printf("Case %d: %d\n",tc++,r);
       
    }
   
    return 0;
}

Read More

UVA 11679 solution

#include<cstdio>
#include<cstring>
using namespace std;

int main()
{
    int b,n,d,c,v,reserve[25],debit[25],credit[25];
    while (scanf("%d%d",&b,&n)==2)
    {
        if (!b && !n) return 0;
        memset(reserve,0,sizeof(reserve));
        memset(debit,0,sizeof(debit));
        memset(credit,0,sizeof(credit));
        for (int i=1;i<=b;i++) scanf("%d",&reserve[i]);
        for (int i=0;i<n;i++)
        {
            scanf("%d%d%d",&d,&c,&v);
            debit[d]+=v;
            credit[c]+=v;
        }
        int flag=1;
        for (int i=1;i<=b;i++)
        {
            if (credit[i]+reserve[i]-debit[i]<0)
            {
                flag=0;
                break;
            }
        }
        if (flag) printf("S\n");
        else printf("N\n");
    }
    return 0;
}

Read More

uva 11428 solution

#include<cstdio>
#include<cmath>
using namespace std;

int main()
{
    int n,cube[70];
    for (int i=0;i<60;i++) cube[i]=i*i*i;
    while (scanf("%d",&n)!=EOF)
    {
        if (n==0) break;
        int i,j,flag=0;
        for (i=0;i<59;i++)
        {
            for (j=i+1;j<60;j++)
                if (cube[j]-cube[i]==n)
                {
                    flag=1;
                    goto print;
                }
        }
        print:
            if (flag) printf("%d %d\n",j,i);
            else printf("No solution\n");
    }
    return 0;
}

Read More

uva 12952 solution

#include<algorithm>
#include<cstdio>
using namespace std;

int main()
{
    int a,b;
    while (scanf("%d%d",&a,&b)!=EOF)
        printf("%d\n",max(a,b));
    return 0;
}

Read More

uva :336 - A Node Too Far

#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;

map<int,bool>visit;

int bfs(map<int , vector <int > >graph, int source, int ttl)
{
    int count=1,f,node,size;
    queue<int > q;
    map<int,int>level;
    level[source]=ttl;
    visit[source]=true;
    q.push(source);
    while (!q.empty())
    {
        f=q.front();
        q.pop();
        if (level[f]==0) break;
        size=graph[f].size();
        for (int i=0;i<size;i++)
        {
            node=graph[f][i];
            if (visit[node]==false)
            {
                q.push(node);
                visit[node]=true;
                level[node]=level[f]-1;
                count++;
            }
        }
    }
    visit.clear();
    return count;
   
}

int main()
{
    int node,edge,case_no=1,a,b,source,ttl;
    while (scanf("%d",&edge) && edge)
    {
        map <int,vector <int > >graph;
        for (int i=0;i<edge;i++)
        {
            scanf("%d%d",&a,&b);
            graph[a].push_back(b);
            graph[b].push_back(a);
            visit[a]=false;
            visit[b]=false;
        }
       
        while (scanf("%d%d",&source,&ttl)==2)
        {
            if (source==0 && ttl==0) break;
            int visited=bfs(graph,source,ttl);
            printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",case_no++,graph.size()-visited,source,ttl);
        }
       
    }
    return 0;
}

Read More

UVA 11340 solution

#include<cstdio>
#include<string.h>
using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,m,v[111],total=0;
        char c[111],s[10005];
        scanf("%d",&n);
        for (int i=0;i<n;i++)
        {
            getchar();
            scanf("%c%d",&c[i],&v[i]);
        }
        scanf("%d",&m);
        getchar();
        while (m--)
        {
            gets(s);
            int l=strlen(s);
            for (int j=0;j<n;j++)
                for (int i=0;i<l;i++)
                    if (c[j]==s[i]) total+=v[j];
        }
        double ans=total/100.0;
        printf ("%.2lf$\n",ans );
    }
    return 0;
}

Read More

uva 11995 solution

#include<cstdio>
#include<stack>
#include<queue>
#include<algorithm>
#include<stdlib.h>
using namespace std;

int main()
{
    int n;
    while (scanf("%d",&n)!=EOF)
    {
        stack<int>s;
        queue<int>q;
        priority_queue<int>pq;
        int stk=1,que=1,pque=1,a,b;
        while (n--)
        {
            scanf("%d%d",&a,&b);
            if (a==1)
            {
                if (stk) s.push(b);
                if (que) q.push(b);
                if (pque) pq.push(b);
            }
            else
            {
                if (stk)
                {
                    if (s.empty() || s.top()!=b) stk=0;
                    else s.pop();
                }
                if (que)
                {
                    if (q.empty() || q.front()!=b) que=0;
                    else q.pop();
                }
                if (pque)
                {
                    if (pq.empty() || pq.top()!=b) pque=0;
                    else pq.pop();
                }
            }
        }
        if (stk+que+pque==0) printf("impossible\n");
        else if (stk+que+pque==1)
        {
            if (stk) printf("stack\n");
            else if (que) printf("queue\n");
            else printf("priority queue\n");
        }
        else if (stk+que+pque>1) printf("not sure\n");
    }
    return 0;
}

Read More