The easiest DFS (depth first search) Problem: UVa 459

N:B First understand the core dfs algorithm and implement it in your own way.There are a lot of resources in online like GeeksForGeeks and in Wiki.


Problem Link: Graph Connectivity
For more practice : Go to here

Source code in C++:

#include<bits/stdc++.h>
#define lli long long int
#define file freopen("in.txt","rt",stdin)
using namespace std;
vector<int> node[101];
int vis[101];
void dfs(int n)
{
    for(int i=0; i<node[n].size(); i++)
    {
        if(vis[node[n][i]]==0)
        {
            vis[node[n][i]] = 1;
            dfs(node[n][i]);
        }
    }
}


int main()
{
    char str[3];
    int test,temp,sum=0;
    char f,s;
    cin>>test;
    scanf("\n");
    while(test--)
    {
        gets(str);
        sum=0;
        temp = str[0];
        memset(vis,0,sizeof vis);
        while(gets(str) and str[0])
        {

            node[str[0]].push_back(str[1]);
            node[str[1]].push_back(str[0]);
        }

        for(int i=65; i<=temp; i++)
        {
            if(vis[i]==0)
            {
                sum++;
                dfs(i);
            }
        }
        cout<<sum;
       if(test)
       {
           cout<<"\n\n";
       }
       else
        cout<<"\n";
       for(int i=65;i<=90;i++)
        node[i].clear();
    }
    return 0;
}

How to represent an odd number sum of any three prime numbers.

Codeforces Number Theory Problem: D - Dima and Lisa 

Tutorial:

There is a fact that the distance between adjacent prime numbers isn't big. For n = 10⁹ maximal distanse is 282. So let's find maximal prime p, such that p < n - 1 (we can just decrease n while it's not prime(we can check it in O(sqrt(n) complexity). We know that n - p < 300. Now we have even (because n and p are odd) number n - p and we should divide it into a sum of two primes. As n - p < 300, we can just iterate over small primes P and check if P is prime and n - p - P is prime. You can check that there is a solution for all even numbers less than 300 by bruteforce.

Source Code in C++:

#include<bits/stdc++.h>
using namespace std;
int mark[1000000],PrimeNumber[1000000];
int n = 1000,nprime,limit;
void PrimeNum()
{
    mark[1]=1;

    PrimeNumber[nprime++]=2;

    for(int i=4; i<=n; i+=2)
        mark[i]=1;

    for(int i=3; i<=n; i+=2)
    {
        if(!mark[i])
        {
            PrimeNumber[nprime++]=i;

            if(i<=limit)
            {
                for(int j=i*i; j<=n; j=j+i*2)
                {
                    mark[j]=1;
                }
            }
        }
    }
}
int main()
{
    limit = sqrt(n+1);
    PrimeNum();
    int a,b;
    bool ok=false;
    cin>>a;
    int prime;
    for(int i=a-1;; i--)
    {
        ok =true;
        for(int j=2; j*j<=i; j++)
        {
            if(i%j==0)
            {
                ok=false;
                break;
            }
        }
        if(ok)
        {
            prime=i;
            break;
        }
    }
    int need = a - prime,got;


    for(int i=0;; i++)
    {

        got = need - PrimeNumber[i];

        ok =true;
        for(int j=2; j*j<=got; j++)
        {
            if(got%j==0)
            {
                ok=false;
                break;
            }
        }
        if(ok)
        {
            b=PrimeNumber[i];
            break;
        }

    }
    if(a==3)
    {
        cout<<1<<"\n"<<3<<endl;
    }
    else if(got==0)
    {
        printf("2\n");
        cout<<prime<<" "<<b<<endl;
    }
    else
    {
        printf("3\n");
        cout<<prime<< " "<<got<< " "<<b<<endl;
    }

    return 0;
}

Easy topological sort problem in C++. UVa-10305

Please don't copy code.At first try to understand the topological sort algorithm.
Best explanation in Bangla Language টপোলজিকাল সর্ট.


Implementation in C++.

Source code:

#include<bits/stdc++.h>
using namespace std;
int result[101];
vector<int>ans;
int main()
{
    vector<int>G[101];

    int n,m;
    while(cin>>n>>m)
    {
        if(n==0 && m==0)
            break;
        ans.clear();
        memset(result,0,sizeof result);
        for(int i=0; i<m; i++)
        {
            int node1,node2;
            cin>>node1>>node2;
            G[node1].push_back(node2);
            result[node2]++;
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(result[j]==0)
                {
                    for(int k=0; k<G[j].size(); k++)
                    {
                        int t = G[j][k];
                        result[t]--;
                    }
                    result[j]=-1;
                    ans.push_back(j);
                    break;
                }
            }

        }
        for(int i=0; i<n; i++)
        {
            cout<<ans[i];
            if(i!=n-1)
                cout<<" ";
        }
        cout<<endl;

        for(int i=0;i<=n;i++)
        {
            G[i].clear();
        }

    }
    return 0;
}

Most easy Disjoint Set Union Problem. UVa-793-Network Connections.

C++ Source Code.
#include<bits/stdc++.h>
using namespace std;

int par[11111];

int find(int a)
{
    if(par[a]==a)
        return a;
    par[a] = find(par[a]);
    return par[a];
}

int main()
{
    int test,i;
    int n,m,computer,u,v;
    int ans1=0,ans2=0;

    char c;
    scanf("%d",&test);

    while(test--)
    {

        scanf("%d",&computer);
        getchar();
        for(i=1; i<=computer; i++)
        {
            par[i] = i;
        }
        ans1=0,ans2=0;
        while((c = getchar())&&isalpha(c))
        {

            scanf("%d%d",&n,&m);
            getchar();
            if(c=='c')
            {
                u = find(n);
                v = find(m);
                par[u] = v;
            }
            else
            {
                u = find(n);
                v = find(m);

                if(u==v)
                {
                    ans1++;
                }
                else
                    ans2++;
            }
        }

        printf("%d,%d\n",ans1,ans2);
        if(test)
            printf("\n");
    }

    return 0;
}