UVA 459 - Graph Connectivity

#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
vector<long>vec[100];
long vis[100]={0},i,j;
long bfs(long source)
{
    long u,v;
    queue<long>que;
    vis[source]=1;
    que.push(source);
    while(!que.empty())
    {
        long u=que.front();
        for(i=0;i<vec[u].size();i++)
        {
            v=vec[u][i];
            if(vis[v]==0)
            {
                que.push(v);
                vis[v]=1;
            }
        }
        que.pop();
    }
}
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        char ch;
        string s;
        long k,k1,k2,i,cnt=0,k3=0,ar[100]={0},vi[100]={0},i1,cnt1=0;
        memset(vis,0,sizeof(vis));
        cin>>ch;
        k=ch-64;
        if(cs!=1)
        {
            cout<<endl;
        }
        cs++;
        getchar();
        while(getline(cin,s))
        {
            if(s[0]=='\0')
                break;
            k1=s[0]-64;
            k2=s[1]-64;
            vec[k1].push_back(k2);
            vec[k2].push_back(k1);
            if(vi[k1]==0)
            {
                cnt1++;
                ar[k3++]=k1;
                vi[k1]=1;
            }
            if(vi[k2]==0)
            {
                ar[k3++]=k2;
                cnt1++;
                vi[k2]=1;
            }
        }
        sort(ar,ar+k3);
        for(i=0;i<k3;i++)
        {
            i1=ar[i];
            if(vis[i1]==0)
            {
                cnt++;
                vis[i1]=1;
                bfs(i1);
            }
        }
        cnt+=(k-cnt1);
        cout<<cnt<<endl;
        for(i=0;i<=30;i++)
        {
            vec[i].clear();
        }
    }
}

longest path in a grid by dfs

#include <stdio.h>

#include <string.h>

#include<bits/stdc++.h>

using namespace std;

long dx[]={-1,-1,-1,0,0,1,1,1};

long dy[]={-1,0,1,-1,1,-1,0,1};

char s[30][30];

long n,vis[100][100]={0},len,cnt=0,i,j;

long dfs(long x,long y)

{

    vis[x][y]=1;

    long i1;

    cnt++;

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

    {

        long x1=x+dx[i1];

        long y1=y+dy[i1];

        if((x1>=0&&x1<len)&&(y1>=0&&y1<len)&&(s[x1][y1]=='1')&&(vis[x1][y1]==0))

        {

            vis[x1][y1]=1;

            dfs(x1,y1);

        }

    }

    return cnt;

}

int main()

{

    long cs=1,ts,i2;

    cin>>ts;

    getchar();

    getchar();

    while(ts--)

    {

        i2=0;

        long mx;

        memset(s,'\0',sizeof(s));

        if(cs!=1)

            cout<<endl;

            cs++;

        memset(vis,0,sizeof(vis));

        while(gets(s[i2]))

        {

            if(s[i2][0]=='\0')

                break;

            i2++;

        }

        len=i2;

        mx=0;

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

        {

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

            {

                if(s[i][j]=='1')

                {

                    cnt=0;

                    dfs(i,j);

                    mx=max(mx,cnt);

                }

            }

        }

        cout<<mx<<endl;

    }

}

UVA 871 - Counting Cells in a Blob

#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
long dx[]={-1,-1,-1,0,0,1,1,1};
long dy[]={-1,0,1,-1,1,-1,0,1};
char s[30][30];
long n,vis[100][100]={0},len,cnt=0,i,j;
long dfs(long x,long y)
{
    vis[x][y]=1;
    long i1;
    cnt++;
    for(i1=0;i1<8;i1++)
    {
        long x1=x+dx[i1];
        long y1=y+dy[i1];
        if((x1>=0&&x1<len)&&(y1>=0&&y1<len)&&(s[x1][y1]=='1')&&(vis[x1][y1]==0))
        {
            vis[x1][y1]=1;
            dfs(x1,y1);
        }
    }
    return cnt;
}
int main()
{

    long cs=1,ts,i2;
    cin>>ts;
    getchar();
    getchar();
    while(ts--)
    {
        i2=0;
        long mx;
        memset(s,'\0',sizeof(s));
        if(cs!=1)
            cout<<endl;
            cs++;
        memset(vis,0,sizeof(vis));
        while(gets(s[i2]))
        {
            if(s[i2][0]=='\0')
                break;
            i2++;
        }
        len=i2;
        mx=0;
        for(i=0; i<len; i++)
        {
            for(j=0;j<len;j++)
            {
                if(s[i][j]=='1')
                {
                    cnt=0;
                    dfs(i,j);
                    mx=max(mx,cnt);
                }
            }
        }
        cout<<mx<<endl;
    }
}

UVA 572 - Oil Deposits

#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
long dx[]={-1,-1,-1,0,0,1,1,1};
long dy[]={-1,0,1,-1,1,-1,0,1};
char s[130][130];
long n,vis[500][500]={0},m;
void dfs(long x,long y)
{
    vis[x][y]=1;
    long i1;
    for(i1=0;i1<8;i1++)
    {

        long x1=x+dx[i1];
        long y1=y+dy[i1];
        if((x1>=0&&x1<n)&&(y1>=0&&y1<m)&&(s[x1][y1]=='@')&&(vis[x1][y1]==0))
        {
            vis[x1][y1]=1;
            dfs(x1,y1);
        }
    }
}
main()
{
    long cs=1;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        long cnt=0,i,j;
        getchar();
        memset(vis,0,sizeof(vis));
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                cin>>s[i][j];
            }
        }
        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                if(s[i][j]=='@'&&vis[i][j]==0)
                {
                    vis[i][j]=1;
                    dfs(i,j);
                    cnt++;
                }
            }
        }
        cout<<cnt<<endl;
    }
}

UVA 352 - The Seasonal War

#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
long dx[]={-1,-1,-1,0,0,1,1,1};
long dy[]={-1,0,1,-1,1,-1,0,1};
char s[30][30];
long n,vis[500][500]={0};
void dfs(long x,long y)
{
    vis[x][y]=1;
    long i1;
    for(i1=0; i1<8; i1++)
    {
        long x1=x+dx[i1];
        long y1=y+dy[i1];
        if(((x1>=0&&x1<n)&&(y1>=0&&y1<n))&&vis[x1][y1]==0)
        {
            vis[x1][y1]=1;
            if(s[x1][y1]=='1')
                dfs(x1,y1);
        }
    }
}
main()
{
    long cs=1;
    while(cin>>n)
    {
        long cnt=0,i,j;
        getchar();
        memset(vis,0,sizeof(vis));
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
                cin>>s[i][j];
            }
        }
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
                if(vis[i][j]==0 && s[i][j]=='1')
                {
                    vis[i][j]=1;
                    dfs(i,j);
                    cnt++;
                }
            }

        }
        printf("Image number %ld contains %ld war eagles.\n",cs++,cnt);
    }
}

UVA 138 - Street Numbers

#include<bits/stdc++.h>
using namespace std;
main()
{
    long long n,x=8,cnt=0;
    double n2;
    while(1)
    {
        n2=sqrt((x*x+x)/2);
        n=n2;
        if(n==n2)
        {
            printf("%10lld%10lld\n",n,x);
            cnt++;
        }
        if(cnt==10)
        break;
        x++;
    }

}

UVA 11080 - Place the Guards

#include<bits/stdc++.h>
using namespace std;
long i,vis[100000]={0};
vector<long>vec[10000];
int bfs(int n)
{
    queue<int>q;
    q.empty();
    long tt[100003]={0},c1=0,c2=1;
    q.push(n);
    vis[n]=1;
    tt[n]=1;
    while(!q.empty())
    {
        int u=q.front();
          q.pop();
          vis[u]=1;
        for(int i=0;i<vec[u].size();i++)
        {
            int v=vec[u][i];
            if(vis[v]==0)
            {
              q.push(v);
              vis[v]=1;
              if(tt[u]==1)
              {
                 tt[v]=2;
                 c1++;
              }
              if(tt[u]==2)
              {
                  tt[v]=1;
                  c2++;
              }
            }
            else
            {
                  if(tt[u]==tt[v])
                    return -1;
            }
        }
    }
    c1=min(c1,c2);
    return c1;
}
main()
{
    long ts;
    cin>>ts;
    while(ts--)
    {
        long a,b,x,y,ans,rs=0;
        cin>>a>>b;
        for(i=0;i<a+5;i++)
        {
            vis[i]=0;
            vec[i].clear();
        }
        for(i=0;i<b;i++)
        {
            cin>>x>>y;
            vec[x].push_back(y);
            vec[y].push_back(x);
        }
        for(i=0;i<a;i++)
        {
            if(vis[i]==0)
            {
                if(vec[i].size()>0)
                {
                    ans=bfs(i);
                    if(ans==-1)
                        break;
                    rs=rs+ans;
                }
                else
                   rs+=1;
            }
            if(ans==-1)
                break;
        }
        if(ans==-1)
            cout<<-1<<endl;
        else
            cout<<rs<<endl;
    }
}