Depth First Search DFS (code (C++)

This algorithm can transverse a graph and find all the reachable points

 1  #include<bits/stdc++.h>

 2  using namespace std;

 3  int n,e;

 4  vector<int>g[128];

 5  bool seen[128];

 6 

 7  void dfs(int u){

 8  seen[u] = true;

 9  cout<<u<<" ";

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

11      int v = g[u][i];

12      if(!seen[v])dfs(v);

13  printf("\n");

14  }

15 

16  }

17  int main(){

18  cin>>n>>e;

19  for(int i=0;i<n;i++){

20      int u,v;

21      cin>>u>>v;

22      g[u].push_back(v);

23  }

24  for(int i = 1;i<=n;i++ ){

25      if(!seen[i]){

26          dfs(i);

27      }

28  }

29 

30  return 0;}

Find the Number Occurring Odd Number of Times in O(n) Time (C++)

Question - We are given an Array(or vector) of integer, in which each element occurs even number of times apart from one element,which occurs odd number of times.
Our job is to find the element with odd occurrence in O(n) time complexity and O(1) Auxiliary space.

The solution is to do bitwise XOR. XOR (^) of all elements gives us odd occurring element. 

#include<bits/stdc++.h>

using namespace std;

void findOddOccuring(int arr[], int size){

int x=0; // Initializing with zero.

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

x^=arr[i];

}

printf("The number appearing odd times is %d\n",x);

//3 occurs odd number of times.Feel free to change

// elements in the array.

}

#include<bits/stdc++.h>

using namespace std;

int main(){

int arr[]={1,2,1,3,4,4,2};

int size = sizeof(arr)/sizeof(arr[0]);

findOddOccuring(arr,size);

return 0;}

Codeforces Problem 950D - A Leapfrog in the Array (C++)

Welcome:
The question to the problem can be found here:

Explanation:

1. It is a tricky one but easy to code if you understand it.
2. using the index of the array we can solve it.
3. First lets test your attention skill. Look at the IV Figure and then the I figure.
4. If the array index number is a odd number(see input) if you add one and divide by 2, you get the required answer(the value at that index)
5. On the other hand as long as the index number is even, do x+=n- x/2.
6. Do them in Bitwise so it will reduce a lot of time to run.
7. Happy Coding.


Code:

#include<bits/stdc++.h>
using namespace std;
int main(){
long long int n,q,x;
cin>>n>>q;
while(q--){
    cin>>x;
    while(!(x&1)){
        x+=n-x/2;
    }
    cout<<(x+1>>1)<<endl;

}



return 0;}

UVA Problem 10685 - Nature (C++)

The question to the problem can be found here:

Explanation:
1. You need to declare two Array, one for Parent and other for number of Children in this case as chains of animals.
2. You need to use MAP data structure to store names as integers.
3. First of all Parents of Node are itself.
4. Take the Names(C) as input Node and Names.
5. Take Relationships between two elements as edges. Now the logical part.
6. If parents of these edges don't match set the 1st name(corresponding int) parent of the 2nd name(corresponding int).
7. Add the array of 2nd to the array of 1st to keep track of size of chain
8. Find the maximum element in the array
9.Happy Coding :)

Code:
#include<bits/stdc++.h>
using namespace std;
int par[5002],arr[5002];
map<string,int>mp;
int find(int n){
if(par[n] == n)
    return n;
return find(par[n]);
}
void check(int u,int v){
int U,V;
U=find(u);
V=find(v);
//cout<<U<<" "<<V<<endl;
if(U!=V){
    par[V]=U;
    arr[U]+=arr[V];
}
}
void makeset(int n){
for(int i=0;i<=n;i++)
par[i]=i;
}

int main(){

string s1,s2,s3;
int node,edge;
while(scanf("%d%d",&node,&edge)==2){
    if(node == 0 && edge ==0){
        break;
    }

    makeset(node);
    for(int i=0;i<node;i++){
        arr[i] = 1;
    }
    for(int i=0;i<node;i++){

        cin>>s1;
        mp[s1]=i;
    }

    for(int i=0;i<edge;i++){
        cin>>s2>>s3;
        int x= mp[s2];
        //cout<<x<<endl;
        int y= mp[s3];
       // cout<<y<<endl;
        check(x,y);
    }
int maximum =0;
for(int i=0;i<node;i++){
    maximum = max(maximum,arr[i]);
}
cout<<maximum<<endl;
}

return 0;}

Codeforces Problem 940A - Points on the line (C++)

Welcome:

The question to the problem can be found here:


Explanation:
1. The diameter is the distance between any two points in the set.
2. Run two nested loops to compare all the elements.
3. Take a variable Ans. It will indicate minimum position in the array to satisfy the number of points taken.
4. Replace ans by comparing each element with all possible elements (ans).
5. Subtract the position ans from the total elements n.
6. Print it and Happy Coding.

Code:

#include<bits/stdc++.h>

using namespace std;

int main(){

int n;

int d;

int k;

cin>>n>>d;

int arr[101];

for(int i=1;i<=n;i++){

    cin>>arr[i];

}

sort(arr+1,arr+n+1);

int ans=0;

for(int i=1;i<=n;i++){

    for(int j=i;j<=n;j++){

        if(arr[j]-arr[i]<=d && j-i+1>ans){

            ans = j-i+1;

        }

    }

}

    cout<<n-ans<<endl;

return 0;}

Codeforces Problem 913A - Modular Exponentiation (C++)

Welcome:

The question to the problem can be found here:


Explanation:
1. Store 2 power n in a temporary variable.
2. x%y if y > x then x remains .
3. If y is smaller print x%y
4. Implement the logic. Happy Coding.

Code:

#include<bits/stdc++.h>
using namespace std;
#define clr(a,replace) memset(a,replace,sizeof(a))
#define INF 99999
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define PB push_back
#define MAX 100000
#define pf printf
#define sf scanf

typedef long long ll;
int main(){
//freopen("input.txt","r",stdin);
  //  freopen("output.txt","w",stdout);
int n,m;
cin>>n>>m;
int res=1;

for(int i=0;i<n;i++){
 res *= 2;
 if(res> m){
cout<<m<<endl;
 return 0;
 }

}
cout<<m%res<<endl;

return 0;}

Uva Problem 544 - Heavy Cargo Solution (C++)

Welcome:

The question to the problem can be found here:


Explanation:

1. The truck size is not needed since the problem can be solved using the lowest cost of path.
2. Use Map function to dynamically point city name(string) to Index(int).
3.++Index means value is increased and then assigned.
4. Use a Modified Floyd Warshal Algorithm as shown below.
5. Every Node in the array d now point to the minimum cost.
6. Finally the source to destination of the array is printed.
7.Happy Coding

Code:

#include<bits/stdc++.h>
using namespace std;
#define clr(a,replace) memset(a,replace,sizeof(a))
#define INF 99999
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define PB push_back
#define MAX 100000
#define LL long long
#define pf printf

int Case=0;
int main(){
//freopen("input.txt","r",stdin);
//   freopen("output.txt","w",stdout);
int n,r;

while(cin>>n>>r){
        if(n==0 && r ==0){
            return 0;
        }

    map<string,int> city;

    string x,y;
    int cost;
    int index=0;
    int d[250][250];
    rep(i,250){
    rep(j,250){
    d[i][j]=-1;
if(i==j){
    d[i][j] =0;
}
    }}
    for(int i=0;i<r;i++){
            cin>>x>>y>>cost;
        if(!city[x]){
            city[x] = ++index;
        }
        if(!city[y]){
            city[y]= ++index;
        }
    d[city[x]][city[y]] =cost;
    d[city[y]][city[x]] =cost;
    }

    for(int k=1;k<=n;k++){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
           d[i][j]=d[j][i] = max(d[i][j],min(d[i][k],d[k][j]));
        }
    }
    }
Case++;
    string source;
    string destination;
    cin>>source>>destination;
    pf("Scenario #%d\n%d tons\n\n",Case,d[city[source]][city[destination]]);

    city.clear();

}


return 0;}

SPOJ Problem ABSP1 Solution in (C++)

Welcome:

The question to the problem can be found here:


Explanation:
1.Notice the array is sorted already.
2. It can be solved with simple Math.
3. There are two logic only.
4. Multiply each element  i -th times(i-th times: position of element in the array)
5. Multiply each element n-1-i -th times.
6. Subtract 4 and 5.
7.Happy Coding !

Code:

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

long long ABS(long long a[],long long n){
    long long sum=0;
rep(i,n){
sum += (a[i]*i) - (a[i]*(n-1-i));
}
return sum;
}
int main(){
 //   freopen("input.txt","r",stdin);
 //freopen("output.txt","w",stdout);
int t;
long long arr[10000];
cin>>t;
while(t-->0){
long long n;
cin>>n;
rep(i,n){
    cin>>arr[i];
}
cout<<ABS(arr,n)<<endl;

}

return 0;}