prefix tree/trie tree.......

#include<bits/stdc++.h>
using namespace std;
struct node
{
    bool endmark;
    node *next[27];
    node()
    {
        endmark=false;
        for(int i=0;i<27;i++)
        next[i]=NULL;
    }
}*root;
void insert(char *str,int len)
{
    node *cur=root;
    for(int i=0;i<len;i++)
    {
        int id=str[i]-'a';
        if(cur->next[id]==NULL)
        cur->next[id]=new node();
        cur=cur->next[id];
    }
    cur->endmark=true;
}
bool search(char *str,int len)
{
    node *cur=root;
    for(int i=0;i<len;i++)
    {
        int id=str[i]-'a';
        if(cur->next[id]==NULL)
        return false;
        cur=cur->next[id];
    }
    return cur->endmark;
}
main()
{
    int i,t,j,m,n;
    cin>>t;
    while(t--)
    {
        root=new node();
        cin>>m;
        while(m--)
        {
            char c[100];
            scanf("%s",c);
            insert(c,strlen(c));
        }
        cin>>n;
        while(n--)
        {
            char d[100];
            scanf("%s",d);
            if(search(d,strlen(d)))
            cout<<"YES"<<endl;
            else
            cout<<"NO"<<endl;
        }
    }
}

topological sort(code)...........

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define Max 1000
#define pb push_back
#define ll long long
using namespace std;
ll indegree[Max];
vector<ll>v[Max];
vector<ll>ans;
ll topsort(ll m)
{
    ll i,j,l,k,taken[Max]={0};
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=m;j++){
        if(indegree[j]==0&&!taken[j]){
        ans.pb(j);
        taken[j]=1;
        l=v[j].size();
        for(k=0;k<l;k++)
        indegree[v[j][k]]--;
        }
        }
    }
}
int main()
{
    ll m,n,i,x,y;
    while(cin>>m>>n)
    {
        if(m==0&&n==0)
        break;
        for(i=1;i<=m;i++)
        indegree[i]=0;
        while(n--)
        {
            cin>>x>>y;
            indegree[y]++;
            v[x].pb(y);
        }
        topsort(m);
        cout<<ans[0];
        for(i=1;i<ans.size();i++)
        cout<<" "<<ans[i];
        cout<<endl;
        for(i=1;i<110;i++)
        v[i].clear();
        ans.clear();

    }

}

struct sort(code)..........

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node
{
    int a;
    int b;
};
bool cmp(const node c1, const node c2) {
return (c1.a < c2.a);
}
int main()
{
    int x;
    node v[5];
    for(int i=0;i<5;i++)
    {
        cin>>x;
        v[i].a=x;
        v[i].b=i;
    }
    sort(v,v+5,cmp);
    for(int i=0;i<5;i++)
    cout<<v[i].b<<" ";
}

prime_sieve(code)............

#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;
bool a[1000001];
void sieve()
{
    long long i,j,m;
    m=sqrt(1000000);
    a[1]=1;
    a[0]=1;
    for(i=3;i<=m;i+=2)
    {
        if(a[i]==0)
        for(j=i*i;j<=1000000;j+=i+i)
        a[j]=1;
    }
}
int main()
{
    sieve();
    long long m;
    while(cin>>m)
    {
        if(m!=2&&m%2==0)
        cout<<"not prime"<<endl;
        else if(a[m]==0)
        cout<<"prime"<<endl;
        else
        cout<<"not prime"<<endl;
    }
}

prime factor(code)...........

#include<iostream>
#include<vector>
#include<cmath>
#define pb(a) push_back(a)
using namespace std;
int main()
{
    long n,i,m;
    vector<long>pfactor;
    cin>>n;
    m=sqrt(n);
    for(i=2;i<=m;i++)
    {
        if(n%i==0)
        while(n%i==0)
        {
            pfactor.pb(i);
            n/=i;
        }
    }
    if(n!=1)
    pfactor.pb(n);
    cout<<"number of factor :"<<pfactor.size()<<endl;
    for(i=0;i<pfactor.size();i++)
    cout<<pfactor[i]<<" ";
}

pair_kahini(code)........

#include<iostream>
#include<algorithm>
#include<vector>v;
#define ll long long
#define pb push_back
using namespace std;
pair<ll,ll>a[1000000];
ll m,i,ans[400000],x;
int main()
{
    cin>>m;
    for(i=0;i<m;i++)
    {
        cin>>a[i].first;
        a[i].second=i;
    }
    sort(a,a+m);
    ans[a[0].second]=a[0].first;
    for(i=1;i<m;i++)
    {
        if(a[i].first<a[i-1].first+1)
        a[i].first=a[i-1].first+1;
        ans[a[i].second]=a[i].first;
    }
    cout<<ans[0];
    for(i=1;i<m;i++)
    cout<<" "<<ans[i];
    cout<<endl;


}

number of co-prime factor of a number(code).....

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
#define pb push_back
long long m,n,k,i,j;
double ans;
vector<double>v;
int main()
{
cin>>m;
ans=double(m);
n=sqrt(m);
k=m;
for(i=2;i<=n;i++)
{
   if(m%i==0)
   {
       v.pb(double(i));
       while(m%i==0)
       m/=i;
       n=sqrt(m);
   }
}
if(m!=1)
v.pb(double(m));
for(i=0;i<v.size();i++)
ans*=double(1-1/v[i]);
cout<<ans<<endl;
}

ncr with table(code)...........

#include<iostream>
using namespace std;
int main()
{
    long long n,r,ncr[31][31];
    for(n=0;n<=30;n++)
    {
        for(r=0;r<=n;r++)
        {
            if(r==0||r==n)
            ncr[n][r]=1;
            else
            ncr[n][r]=(ncr[n-1][r]+ncr[n-1][r-1]);
        }
    }
    while(cin>>n>>r)
    cout<<ncr[n][r]<<endl;
}

mod of n^p(code)..........

// determine (n^p)%m
#include<iostream>
using namespace std;
long m,n,p;
long mod(long a,long b)
{
    if(b==0)
    return 1;
    if(b%2==0)
    {
        long ret;
        ret=mod(a,b/2);
        return ((ret%m)*(ret%m))%m;
    }
    else
    return ((a%m)*(mod(a,b-1)%m))%m;
}
int main()
{
    while(cin>>n>>p>>m)
    {
        cout<<mod(n,p)<<endl;

    }
}

number of digit of factorial n(n!)(code)............

#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    long long i;
    long double n,ans;
    while(cin>>n){                //factorial n
    ans=0;
    for(i=1;i<=n;i++)
    ans+=log10(i);
    ans=floor(ans)+1;
    cout<<ans<<endl;;
    }

}

Bisection(code)....

#include<iostream>
#include<cmath>
#define EPS .00001
using namespace std;
bool equal(double y,double val)
{
    if(abs(y-val)<EPS)
    return true;
    else
    return false;
}
double bisection(double l,double u,double val)
{
    double mid=(l+u)/2;
    double y=mid*mid;
    bool isequal=equal(y,val);
    if(isequal)
    return mid;
    else if(y>val)
    return  bisection(l,mid,val);
    else
    return bisection(mid,u,val);

}
int main()
{
    double b;
    cin>>b;
    cout<<"square root of "<<b<<" by bisection method : "<<bisection(0,50,b)<<endl;
}

Big mod......(b^p)%m(code)............

#include<iostream>
#include<stdio.h>
using namespace std;
long b,m;
long b_mod(long p)
{
    if(p==0)                //(b^p)%m solution
    return 1;
    if(p%2==0)
    {
        long ret=b_mod(p/2);
        return ((ret%m)*(ret%m))%m;
    }
    else
    return ((b%m)*(b_mod(p-1)%m))%m;
}
int main()
{
    long p,i;
    while(scanf("%ld%ld%ld",&b,&p,&m)==3)
    {
        cout<<b_mod(p)<<endl;
    }
}

bfs with queue(code)......

#include<iostream>
#include<queue>
#define max 1000
using namespace std;
vector<int>graph[max];
void bfs(int node,int source)
{
    int u,v,i;
    queue<int>que;
    int taken[max]={0};
    taken[source]=1;
    int distance[max];
    distance[source]=0;
    que.push(source);
    while(!que.empty())
    {
        int u=que.front();
        for(int i=0;i<graph[u].size();i++)
        {
            v=graph[u][i];
            if(taken[v]==0)
            {
                distance[v]=distance[u]+1;
                que.push(v);
                taken[v]=1;
            }
        }
        que.pop();
    }
    for(i=1;i<=node;i++)
    {
        cout<<"distance from source ::  ";
        cout<<distance[i]<<endl;
    }
}
int main()
{
    int node,edge,i,x,y,j;
    cin>>node>>edge;
    for(i=1;i<=edge;i++)
    {
        cin>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    int source;
    cin>>source;
    bfs(node,source);

}