Minimum cost of a friend circle by using UNION FIND

এইটা Union Find টপিকস রিলেটেড

প্রবলেম লিঙ্কঃ http://codeforces.com/contest/893/problem/C

পুরো কোড সবার নিচে

দেখা যাবে দেওয়া থাকলো ৫ টা মান

ইনপুটঃ-

৫ ২           //৫ হল ৫ টা মান আর ২ হল ২ টা বন্ধুর লিস্ট

৮ ৫ ৩ ৪ ২   // এইগুলো হল পজিশন অনুযায়ী এদের ওয়েট যেমন ১ এর ৮,২ এর ৫ ,৩ এর ৩ ,৪ এর ৪ ,৫ এর ২

১ ৪          // ৪ ও ১ বন্ধু

৪ ৫         // ৪ ও ৫ বন্ধু

আউটপুটঃ-১০

এখন ১ ৪ ৫ একটা দল ,২ একটা দল,৩ একটা দল

এদের মধ্যে সব গুলো দলের মিনিমাম ওয়েট এর যোগফল কত?

উত্তর=১০

কারণ ১,৪,৫ এই দলের মিনিমাম ২+২ এর দলের ৫+৩ এর দলের ৩=১০

একটা কোড যদি করা থাকে সবার প্যারেন্ট কে এইবার মিনিমাম ওয়েট কিভাবে পাবো?

সেইটার কোডঃ

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

        {

            par[i]=Find(i);

            st.insert(par[i]);

            mn[par[i]]=min(mn[par[i]],ar[i]);

            cout<<mn[par[i]]<<endl;

        }

set<long long >::iterator it;

        for(it=st.begin(); it!=st.end(); it++)

        {

            ans+=mn[*it];

        }

        cout<<ans<<endl;

পুরো কোডঃ-

#include <bits/stdc++.h>

using namespace std;

//long long vis[100010],ar[100010];

//vector<long long>vec[100010];

long long n,k;

long long par[100010],ar[100010],mn[100005];

long long Find(long long xx)

{

    if(par[xx]==xx)

        return xx;

    return par[xx]=Find(par[xx]);

}

void make_union(long long x,long long y)

{

    par[Find(y)]=Find(x);

}

set<long long>st;

main()

{

    //long k;

    cin>>n>>k;

    {

        long long i,u1,v1,ans=0;

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

        {

            cin>>ar[i];

            mn[i]=ar[i];

            par[i]=i;

        }

        for(i=1; i<=k; i++)

        {

            cin>>u1>>v1;

            make_union(u1,v1);

        }

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

        {

            par[i]=Find(i);

            st.insert(par[i]);

            mn[par[i]]=min(mn[par[i]],ar[i]);

            cout<<mn[par[i]]<<endl;

        }

        set<long long >::iterator it;

        for(it=st.begin(); it!=st.end(); it++)

        {

            ans+=mn[*it];

        }

        cout<<ans<<endl;

    }

}

Print 1 to 100 without for loop

#include<bits/stdc++.h>
using namespace std;
int i=1;
class A
{
    //int i=1;
public:
    A()
    {
        printf("%d\n",i++);
    }
};
//int A:: i=1;
main()
{
    A obj[100];
}

UVA 443 - Humble Numbers

#include<bits/stdc++.h>
using namespace std;
vector<long long>vec;
void calc()
{
    long i,i1,i2,i3;
    for(i=0;i<31;i++)
    {
        for(i1=0;i1<20;i1++)
        {
            for(i2=0;i2<14;i2++)
            {
                for(i3=0;i3<12;i3++)
                {
                    long long ans=pow(2,i)*pow(3,i1)*pow(5,i2)*pow(7,i3);
                    if(ans>0)
                        vec.push_back(ans);
                }
            }
        }
    }
    sort(vec.begin(),vec.end());
}
main()
{
    calc();
    long n;
    while(cin>>n)
    {
        if(n==0)
            break;
        printf("The %d", n);
        if(n%10 == 1 && n%100 != 11)
            printf("st");
        else if(n%10 == 2 && n%100 != 12)
            printf("nd");
        else if(n%10 == 3 && n%100 != 13)
            printf("rd");
        else
            printf("th");
        printf(" humble number is %d.\n",vec[n-1]);
    }
}

UVA 12582 - Wedding of Sultan

#include<bits/stdc++.h>
using namespace std;
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        string s;
        long i,x;
        stack<char>st;
        cin>>s;
        st.push(s[0]);
        st.push(s[1]);
        long sz=s.size(),ar[100]={0};
        printf("Case %ld\n",cs++);
        for(i=2;i<sz-1;i++)
        {
            if(s[i]==st.top())
            {
                x=s[i]-'A';
                ar[x]++;
                st.pop();
                x=st.top()-'A';
                ar[x]++;
            }
            else
                st.push(s[i]);
        }
        for(i=0;i<26;i++)
        {
            if(ar[i]!=0)
            cout<<(char)(i+65)<<" = "<<ar[i]<<endl;
        }
    }
}

UVA 12583 - Memory Overflow

#include<bits/stdc++.h>
using namespace std;
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        long n,sz,i,cnt=0;
        char ch;
        string s;
        map<char,long>mp;
        queue<char>q;
        cin>>n>>sz>>s;
        for(i=0;i<sz;i++)
        {
            q.push(s[i]);
            if(mp[s[i]]!=0)
                cnt++;
            mp[s[i]]++;
        }
        for(i=sz;i<n;i++)
        {
            ch=q.front();
            if(mp[s[i]]!=0)
                {
                    cnt++;
                }
            mp[ch]--;
            mp[s[i]]++;
            q.pop();
            q.push(s[i]);
        }
        printf("Case %ld: %ld\n",cs++,cnt);
    }
}

UVA 12898 - And Or

Explaintion:
Step 1: Count bit length of a and b
step 2: if lenb>lena then OR = 2^lenb - 1 and And = 0*/
step 3: find/count not change bits between a and b, from MSB to LSB
        Or = b | R
         And = b | ~R  where R contain's 1 (total 1 = count)

Example:
[1]a = 7  b = 8

lena = 3 , Lenb = 4

 so Or = 2^lenb - 1 = 16 - 1 = 15

And = 0

[2] Let a = 12 , b =15

lena = 4, len b = 4
a = 1100 , b = 1111

start j = 3 and break when j = 1

R = 1LL<<(j+1) - 1 = (11)2
unchanged first 2 bits
Or = b | R = (1111) = 15
And = b & ~R = (1100) = 12

Source Code:
#include<bits/stdc++.h>
using namespace std;
#define maxlen 61
typedef long long ll;
int main()
{
    int n,c,i,lena,lenb,j;
    int a1[maxlen],b1[maxlen];
    ll Or,And,x,a,b,R;
    const ll one = 1;
    scanf("%d",&n);
    for(i = 1; i <= n; i++)
    {
        scanf("%lld %lld",&a,&b);
        /*Step 1: Count bit length of a and b*/
        c = 0;
        x = a;
        while(x)
        {
            a1[c] = x&1;
            x >>= 1;
            c++;
        }
        lena = c;
        c = 0;
        x = b;
        while(x)
        {
            b1[c] = x&1;
            x >>= 1;
            c++;
        }
        lenb = c;
        /*step 2: if lenb>lena then OR = 2^lenb - 1 and And = 0*/
        /*step 3: find/count not change bits between a and b, from LSB to MSB
                  Or = b | R and And = b | ~R  where R contain's 1 (total 1 = count)
         */
        if(lenb>lena)
        {
            Or =(one<<lenb)-1;
            And = 0;
        }
        else
        {
            for( j = lenb-1; j >= 0; j--)
            {
                if(a1[j]!=b1[j]) break;
            }
            R = (one<<(j+1))-1;
            Or = b|R;
            And = b&~R;
        }
        printf("Case %d: %lld %lld\n",i,Or,And);
    }
    return 0;
}

UVA 1726 - Automatic Cheater Detection

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
#define nl         printf("\n")
#define case(a,b)  printf("Case %lld: %lld\n",a,b)
#define P(a)       printf("%lld\n",a)
#define SP(a)      printf("%lld ",a)
#define G(a)       scanf("%lld",&a)
#define GG(a,b)    scanf("%lld %lld",&a,&b)
#define pb         push_back
#define DB         printf("I WAS HERE\n")
#define SPP(a,b)   printf("%lld %lld\n",a,b)
#define LL         long long
int main()
{
    long long t;
    G(t);
    while(t--)
    {
        LL n;
        G(n);
        long long ar[12]={0},ar2[12]={0};
        char r[10];
        long long i,j,d,s,cnt=0;
        for(i=1;i<=n;i++)
        {
            scanf("%lld %lld %s",&d,&s,r);
            if(s==0 && r[0]=='i')
            {
                ar[d]++;
            }
            else if(s==1 && r[0]=='c')
            {
                ar2[d]++;
            }
        }
        cnt=0;
        for(i=1;i<=9;i++)
        {
            for(j=i+1;j<=10;j++)
            {
               LL x=ar[i]*ar2[j];
                cnt+=x;
            }
        }
        P(cnt);
    }

return 0;
}

UVA 1729 - Owllen

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        string s;
        cin>>s;
        long mp[100]={0},i,mn=100000000;
        for(i=0;i<s.size();i++)
        {
            mp[s[i]-97]++;
        }
        for(i=0;i<26;i++)
        {
            mn=min(mp[i],mn);
        }
        printf("Case %ld: ",cs++);
        cout<<mn<<endl;
    }
}

UVA 1727 - Counting Weekend Days

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long ts;
    cin>>ts;
    while(ts--)
    {
        string s,s1;
        cin>>s>>s1;
        map<string,long>mp;
        mp["SUN"]=1;
        mp["MON"]=2;
        mp["TUE"]=3;
        mp["WED"]=4;
        mp["THU"]=5;
        mp["FRI"]=6;
        mp["SAT"]=0;
        int i,tot;
        if(s=="JAN"||s=="MAR"||s=="MAY"||s=="JUL"||s=="AUG"||s=="OCT"||s=="DEC")
        {
            tot=31;
        }
        else if(s=="FEB")
            tot=28;
        else tot=30;
        int x=mp[s1],x1,ans=0;
        x1=x;
        for(i=1;i<=tot;i++)
        {
            if(x%7==0||x%7==6)
                ans++;
            x++;
        }
        cout<<ans<<endl;
    }
}

UVA 1180 - Perfect Numbers

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long n;
    while(cin>>n)
    {
        string s;
        cin>>s;
        s+=',';
        long i,p=0;
        for(i=0; i<s.size(); i++)
        {
            if(s[i]==',')
            {
                if( p == 2 || p == 3 || p == 5 || p == 7 || p == 13 || p == 17 || p == 19 )
                    printf("Yes\n") ;
                else printf("No\n");
                p=0;
            }
            else
            {
                p=p*10+s[i]-48;
            }
        }
    }
}

UVA 10140 - Prime Distance

#include <bits/stdc++.h>
using namespace std;
#define mx 48000
long long vis[48000]= {0},ar[48000]= {0},i,j,k=0;
vector<long long >vec;
void sieve()
{
    for(i=4; i<=mx; i+=2)
        vis[i]=1;
    for(i=3; i<=sqrt(mx); i+=2)
    {
        if(vis[i]==0)
        {
            for(j=2*i; j<=mx; j+=i)
            {
                vis[j]=1;
            }
        }
    }
    vis[1]=1,vis[0]=1;
    for(i=1; i<=mx; i++)
    {
        if(vis[i]==0)
        {
            ar[k++]=i;
        }
    }
}
bool chk(long long nm)
{
    if(nm>=k)
    {
        for(long long i1=0; i1<k&&ar[i1]<=sqrt(nm); i1++)
        {
            if(nm%ar[i1]==0)
            {
                return 0;
            }
        }
        return 1;
    }
    else
    {
        if(vis[i]==0)
            return 1;
        else
            return 0;
    }
}
main()
{
    sieve();
    long long l,u;
    while(cin>>l>>u)
    {
        for(i=l; i<=u; i++)
        {
            if(chk(i))
            {
                vec.push_back(i);
            }
        }
        long long ll=vec.size(),dif=0,dif2,dif1,f=0,f1=0;
        if(ll<2)
            printf("There are no adjacent primes.\n");
        else
        {
            for(i=1; i<ll; i++)
            {
                if(i==1)
                {
                    dif=vec[i]-vec[i-1];
                    dif1=vec[i]-vec[i-1];
                    f=f1=i;
                }
                else
                {
                    dif2=vec[i]-vec[i-1];
                    if(dif2<dif)
                    {
                        f=i;
                        dif=dif2;
                    }
                    if(dif2>dif1)
                    {
                        dif1=dif2;
                        f1=i;
                    }
                }
            }
            printf("%lld,%lld are closest, %lld,%lld are most distant.\n",vec[f-1],vec[f],vec[f1-1],vec[f1]);
        }
        vec.clear();
    }
}

UVA 10751 - Chessboard

#include <cstdio>

#include <cmath>

using namespace std;

int main()

{

    int tc, n;

    scanf("%d", &tc);

    while (tc--)

    {

        scanf("%d", &n);

        if (n > 1)

            printf("%.3lf\n", (4 * n - 4) + sqrt(2) * (n - 2) * (n - 2));

        else

            printf("0.000\n");

    }

    return 0;

}

UVA 10137 - The Trip

#include<bits/stdc++.h>
using namespace std;
main()
{
    long n;
    while(cin>>n)
    {
        if(n==0)
            break;
        long i;
        double ar[10010]= {0.0},sum=0.0,avg=0;
        for(i=0; i<n; i++)
        {
            cin>>ar[i];
            sum+=ar[i];
        }
        avg=sum/n;
        sum=0.0;
        double sum1=0.0,baki;
        long ans=0;
        for(i=0; i<n; i++)
        {
            baki=avg-ar[i];
            if(baki>0)
            {
                ans=(baki*100);
                sum=sum+ans;
            }
            else
            {
                baki=baki*-1;
                ans=(baki*100);
                sum1=sum1+ans;
            }
        }
        if(sum>sum1)
            printf("$%.2lf\n",sum/100.0);
        else
            printf("$%.2lf\n",sum1/100.0);
    }
}

UVA 12160 - Unlock the Lock

#include<bits/stdc++.h>
using namespace std;
long vis[10005],dist[10005],i,l,u,r,ar[15];
void bfs(long src)
{
    queue<long>q;
    q.push(src);
    vis[src]=0;
    dist[src]=0;
    while(!q.empty())
    {
        long u1=q.front();
        q.pop();
        for(i=0;i<r;i++)
        {
            long v=(u1+ar[i])%10000;
            if(vis[v]==0)
            {
                vis[v]=1;
                dist[v]=dist[u1]+1;
                q.push(v);
            }
        }
    }
}
main()
{
    long cs=1;
    while(cin>>l>>u>>r)
    {
        if(l==0&&u==0&&r==0)
            break;
        for(i=0;i<r;i++)
        {
            cin>>ar[i];
        }
        bfs(l);
        printf("Case %ld: ",cs++);
        if(dist[u]==0)
            printf("Permanently Locked\n");
        else
        cout<<dist[u]<<endl;
        for(i=0;i<10005;i++)
        {
            vis[i]=0;
            dist[i]=0;
        }
    }
}

UVA 12917 - Prop hunt!

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

int main()
{
    int a,b,c;
    while(cin>>a>>b>>c)
    {
        if((a+b)>c)
            cout<<"Hunters win!"<<endl;
        else
            cout<<"Props win!"<<endl;
    }
}

UVA 1112 - Mice and Maze

#include<bits/stdc++.h>
using namespace std;
vector<long>vec[105],cost[105];
long sorc,desti;
long dist[105];
struct node
{
    long u,w;
    node(long a,long b)
    {
        u=a;
        w=b;
    }
    bool operator < ( const node& p ) const
    {
        return w > p.w;
    }
};
void dijkstra(long s)
{

    priority_queue<node>pq;
    dist[s]=0;
    pq.push(node(s,0));
    while(!pq.empty())
    {
        node top=pq.top();
        pq.pop();
        long u=top.u;
        for(long i=0;i<(long)vec[u].size();i++)
        {
            long v=vec[u][i];
            if(dist[u]+cost[u][i]<dist[v])
            {
                dist[v]=dist[u]+cost[u][i];
                pq.push(node(v,dist[v]));
            }
        }
    }
}
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        if(cs>1)
            cout<<endl;
        long i,n,e;
        cin>>n>>desti>>sorc>>e;
        for(long i=1; i<=n; i++)
        dist[i]=100000000;
        for(i=0;i<e;i++)
        {
            long u,v,w;
            cin>>u>>v>>w;
            vec[u].push_back(v);
            vec[v].push_back(u);
            cost[u].push_back(w);
            cost[v].push_back(w);
        }
        long cnt=0;
        dijkstra(desti);
        for(i=1;i<=n;i++)
        {
            if(dist[i]<=sorc)
                cnt++;
        }
        cs++;
        cout<<cnt<<endl;
        for(i=1;i<=n;i++)
        {
            cost[i].clear();
            vec[i].clear();
        }
    }
}

UVA 10986 - Sending email

#include<bits/stdc++.h>
using namespace std;
vector<long>vec[200002],cost[200002];
long sorc,desti;
long dist[200002];
struct node
{
    long u,w;
    node(long a,long b)
    {
        u=a;
        w=b;
    }
    bool operator < ( const node& p ) const
    {
        return w > p.w;
    }
};
long dijkstra(long n)
{
    for(long i=0; i<=n; i++)
        dist[i]=10000000;
    priority_queue<node>pq;
    dist[sorc]=0;
    pq.push(node(sorc,0));
    while(!pq.empty())
    {
        node top=pq.top();
        pq.pop();
        long u=top.u;
        if(u==desti)
        {
            return dist[desti];
        }
        for(long i=0;i<(long)vec[u].size();i++)
        {
            long v=vec[u][i];
            if(dist[u]+cost[u][i]<dist[v])
            {
                dist[v]=dist[u]+cost[u][i];
                pq.push(node(v,dist[v]));
            }
        }
    }
    return -1;
}
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        long i,n,e;
        cin>>n>>e>>sorc>>desti;
        for(i=0;i<e;i++)
        {
            long u,v,w;
            cin>>u>>v>>w;
            vec[u].push_back(v);
            vec[v].push_back(u);
            cost[u].push_back(w);
            cost[v].push_back(w);
        }
        long ans=dijkstra(n);
        if(ans==-1)
            printf("Case #%ld: unreachable\n",cs++);
        else
            printf("Case #%ld: %ld\n",cs++,ans);
        for(i=0;i<n;i++)
        {
            cost[i].clear();
            vec[i].clear();
        }
    }
}

UVA 429 - Word Transformation

#include<bits/stdc++.h>
#define fr(i1,m) for(int i1=0;i1<m;i1++)
using namespace std;
vector<int>vc[10000];
int  bfs(int n,int m)
{
    queue<int>q;
    q.push(n);
    int t[100000]= {0},d[100000]= {0};
    t[n]=1;
    d[n]=0;
    while(!q.empty())
    {
        int u=q.front();
        if(u==m)
            return d[u];
        for(int i=0; i<vc[u].size(); i++)
        {
            int v=vc[u][i];
            if(!t[v])
            {
                d[v]=d[u]+1;
                t[v]=1;
                q.push(v);
            }
        }
        q.pop();
    }
}

int main()
{
    long n;
    scanf("%ld",&n);
    fr(ii,n)
    {
        if(ii>0)
            cout<<"\n";
        long p=0,l=1,hh,j,c;
        char ch[100000];
        string s[10000],s1,ff,f,kk,rr;
        map<string,int>mp;
        while(cin>>s1)
        {
            if(s1=="*")
                break;
            s[p]=s1;
            mp[s1]=l++;
            p++;

        }
        fr(i,p)
        {
            for(j=i+1; j<p; j++)
            {
                if(s[i].size()==s[j].size())
                {
                    hh=0;
                    kk=s[j];
                    rr=s[i];

                    fr(k,s[i].size())
                    {
                        if(rr[k]!=kk[k])
                        {
                            hh++;
                            if(hh>1)
                                break;
                        }
                        if(hh>1)
                            break;
                    }
                    if(hh==1)
                    {
                        vc[mp[rr]].push_back(mp[kk]);
                        vc[mp[kk]].push_back(mp[rr]);
                    }
                }
            }
        }
        getchar();
        //  scanf("\n");
        while(gets(ch))
        {
            if(ch[0]=='\0')
                break;
            f="";
            ff="";
            c=0;
            fr(i,strlen(ch))
            {
                if(ch[i]==' ')
                    c=1;
                else if(c==0)
                    f+=ch[i];
                else
                    ff+=ch[i];

            }
            cout<<f<<" "<<ff<<" "<<bfs(mp[f],mp[ff])<<"\n";
        }
        fr(i,l+4)
        vc[i].clear();

    }
    return 0;
}