UVA 445 - Marvelous Mazes(c file)

Problem Type :  String


#include<stdio.h>
#include<string.h>
int main()
{
    char ch[200];
    int i,j,cou;
    while(gets(ch))
    {
        int len = strlen(ch);
        cou=0;
        for(i=0; i<len; i++)
        {
            if(ch[i]=='!')
            {
                printf("\n");
            }
            else if(ch[i]=='0'){
                cou+=0;
            }
            else if(ch[i]=='1')
            {
               cou+=1;
            }
            else if(ch[i]=='2')
            {
                cou+=2;
            }else if(ch[i]=='3')
            {
                cou+=3;
            }
            else if(ch[i]=='4')
            {
                cou+=4;
            }
            else if(ch[i]=='5')
            {
                cou+=5;
            }
            else if(ch[i]=='6')
            {
                cou+=6;
            }
            else if(ch[i]=='7')
            {
                cou+=7;
            }
            else if(ch[i]=='8')
            {
                cou+=8;
            }
            else if(ch[i]=='9')
            {
                cou+=9;
            }
            else if(ch[i]>=65 && ch[i]<=90|| ch[i]=='*')
            {
                for(j=0;j<cou;j++)
                {
                    printf("%c",ch[i]);
                }
                cou=0;
            }
            else if(ch[i]=='b')
            {
                for(j=0;j<cou;j++)
                {
                    printf(" ");
                }
                cou=0;
            }


        }
        printf("\n");
    }
}

UVA 11080 - Place the Guards(cpp file)

Problem Type : Bipartite Graph Check


#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#define MAX 201
using namespace std;

int node,edge,color[MAX],g=0,w=0,cou;
vector<int >mat[MAX];
char color1[MAX];
int BFS(int s)
{
    queue<int> q;
    q.push(s);
    color[s]=1;
    int tot=0,black=0;

    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        tot++;
        if (color[u]==1)
            black++;

        for (int i=0; i<mat[u].size(); i++)
        {

                int   v=mat[u][i];
                if (color[v]==2)
                {
                    color[v]=1-color[u];
                    q.push(v);
                }
                else if (color[v]==color[u])
                {
                    return -1;
                }


        }

    }
    if (tot==1)
        return 1;
    return min(black,tot-black);
}
int main()
{
    int i,j ,k,test,n,m,ans;
    scanf("%d",&test);
    while(test--)
    {
        for(i=0;i<MAX;i++)
        {
            mat[i].clear();
        }
        scanf("%d %d",&node,&edge);
        for(i=1; i<=edge; i++)
        {
            scanf("%d %d",&n,&m);
            mat[n].push_back(m);
            mat[m].push_back(n);

        }
        for(i=0; i<node; i++)
        {
            color[i]=2;
        }
        cou=0;
        ans=0;
        for (int i=0; i<node; i++)
        {
            if (color[i]==2)
            {
                int x=BFS(i);
                if (x==-1)
                {
                    printf("-1\n");
                    cou=-1;
                    break;
                }

                else ans+=x;

            }
        }
        if(cou==0)
        {
            printf("%d\n",ans);
        }
    }

}

/*

input:
1
13 12
0 8
1 8
2 9
3 9
4 10
5 10
6 11
7 11
8 12
9 12
10 12
11 12

output:
4

*/

UVA 534 - Frogger(cpp file)

Problem Type : MST + floyd Warshall


Code :


#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define MAX 201
using namespace std;
double arr[MAX][MAX];


int main()
{
    int i,j,k,len,x[MAX],y[MAX],node,cou=0;
    double px,py,ux;
    while(scanf("%d",&node)&&node)
    {
        cou++;
        for ( int i = 0; i < node; i++ )
        {
            scanf ("%d %d", &x [i], &y [i]);
        }
        for(i=0; i<node; i++)
        {
            for(j=i+1; j<=node; j++)
            {
                px=pow((x[i]-x[j]),2);
                py=pow((y[i]-y[j]),2);
                ux=sqrt(px+py);
                arr[i][j]=arr[j][i]=ux;
            }
        }
        for(k=0; k<node; k++)
        {
            for(i=0; i<node; i++)
            {
                for(j=0; j<node; j++)
                {
                    if(arr[i][j]!=0 && arr[i][k]>0 && arr[k][j]>0)
                    {
                        arr[i][j]=min(arr[i][j],max(arr[i][k],arr[k][j]));
                    }
                }
            }
        }
        printf("Scenario #%d\n",cou);
        printf("Frog Distance = %.3lf\n\n",arr[0][1]);
        memset(arr,0,sizeof(arr));
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
    }

}

Strongly Connected Component (cpp file)

Strongly Connected Component Algorithm

Code :

#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 100
vector<int>vcc[MAX],vcc1[MAX],collect;
int vertex ,edge,color[MAX];
void topsort(int n)
{
    color[n]=1;
    int i;
    for(i=0; i<vcc[n].size(); i++)
    {
        if(color[vcc[n][i]]==0)
        {
            topsort(vcc[n][i]);
        }
    }
    collect.push_back(n);
}
void dfs(int n)
{
    color[n]=1;
    int i;
    for(i=0; i<vcc1[n].size(); i++)
    {
        if(color[vcc1[n][i]]==0)
        {
            printf("->%d",vcc1[n][i]);
            dfs(vcc1[n][i]);
        }
    }
}
int main()
{
    int i,j,k,len,n,m;
    scanf("%d %d",&vertex,&edge);
    for(i=1; i<=edge; i++)
    {
        scanf("%d %d",&n,&m);
        vcc[n].push_back(m);
        vcc1[m].push_back(n);
    }
    for(i=1; i<=vertex; i++)
    {
        if(color[i]==0)
        {
            topsort(i);
        }
    }
    std::reverse(collect.begin(), collect.end());
    memset(color,0,sizeof(color));
    int cou =0;
    printf("Strongly connected path : \n");
    for(i=0; i<collect.size(); i++)
    {


        if(color[collect[i]]==0)
        {
            cou++;
            printf("%d",collect[i]);
            dfs(collect[i]);

            printf("\n");
        }

    }
    printf("\n%d strongly connected component found\n",cou);


}

Codeforces Pangram

Problem Type :

 

implementation

 

 

 

 

strings

#include<stdio.h>

#include<ctype.h>

#include<string.h>

#define MAX 101

int main()

{

    long int i1,len,arr1[MAX];

    char arr[MAX],c1;

    while(scanf("%ld",&len)==1)

    {

        getchar();

        for(i1=0; i1<len; i1++)

        {

            scanf("%c",&arr[i1]);

            c1=toupper(arr[i1]);

            arr1[c1]=1;

        }

        int cou=0;

        for(i1=65; i1<=90; i1++)

        {

            if(arr1[i1]==1)

                continue;

            else

            {

                cou=1;

                break;

            }

        }

        if(cou==1)

        {

            printf("NO\n");

        }

        else

        {

            printf("YES\n");

        }

        memset(arr1,0,sizeof(arr1));

    }

}