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;}