template shob eksathe

BFS --------Start----------
#include<bits/stdc++.h>

#define MAXX 105

using namespace std;

bool visit[MAXX];

vector <int> edges[MAXX];


int level[MAXX];
int cnt[MAXX];

int res=0;

void BFS(int x)
{

    for(int i=0;i<MAXX;i++)
    {
        visit[i]=false;
        level[i]=0;
        //cnt[i]=0;
    }

    queue <int> q;

    level[x]=0;
    visit[x]=true;
    q.push(x);


    while(!q.empty())
    {
        int src= q.front();
       // cout<<src <<" ";
        q.pop();

         int sz = edges[src].size();

        for( int i=0;i<sz; ++i)
        {
	    int des=edges[src][i];
            if(visit[des]==false)
            {

                visit[des]=true;
                level[des]= level[src]+1;
                q.push(des);


            }
        }
    }

}

int main()
{

    //freopen("input.txt","r",stdin);
    int t,cs=1;
    int edge,node;

    cin>>t;

    while(t--)
    {
       scanf("%d%d",&node,&edge);
        int x,y;
        int a,b;

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

        for(int i=1;i<=edge;++i)
        {
            scanf("%d%d",&x,&y);

            edges[x].push_back(y);
            edges[y].push_back(x);
        }



        BFS(0);

        printf("Case %d: %d\n",cs,res);
        cs++;



    }






    return 0;
}



BFS --------End----------

Dijkstra---start-----

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

#define pb push_back
#define sz size()
#define x first
#define y second
#define N 100010
typedef long long ll;
typedef pair<int,ll>pii;
typedef vector<pii>vii;
const ll oo=(ll)1e18;
bool debug;
int n,m,a,b,c,par[N];
ll dist[N];
vii g[N];
vector<int>v;

struct cf{
    bool operator()(const pii &a,const pii &b)const{
        return (a.y>b.y);
    };
};
void print_graph()
{   cout<<endl;
    for(int i=0;i<n;i++)
    {
        int siz=g[i].size();
        cout<<i<<"-> ";
        for(int j=0;j<siz;j++)
        {
            cout<<g[i][j].first<<","<<g[i][j].second<<" ";
        }
        printf("\n");

    }
    cout<<endl;
}

void path_print(int index)
{
    if(par[index]==-1)
    {

        return;

    }


    path_print(par[index]);

     printf("%d ",par[index]);

     // cout<<0<<" ";


}

int main(){
    debug=0;
    freopen("input1.txt","r",stdin); ///file reading
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&c);

        g[a].pb(pii(b,c));
      ///  g[b].pb(pii(a,c));
    }

    print_graph();

    priority_queue<pii,vii,cf>q;

    for (int i=0;i<n;i++)
        dist[i]=oo;

    q.push(pii(0,0));
    par[0]=-1;
    dist[0]=0;
    while (!q.empty()){
        pii top=q.top();
        q.pop();
        int v=top.x;
        ll d=top.y;
        if (d<=dist[v]){
            for (vii::iterator it=g[v].begin();it!=g[v].end();it++){
                int v2=it->x;
                ll d2=it->y;
                if (dist[v2]>dist[v]+d2){
                    dist[v2]=dist[v]+d2;
                    par[v2]=v;
                    q.push(pii(v2,dist[v2]));
                }
            }
        }
    }


    for(int i=0;i<n;i++)
    {
        printf("node: %d path: ",i);
        path_print(i);
        printf("%d  cost: %lld\n",i,dist[i]);
    }

    return 0;
}


Dijkstra----End------

BFS_2D_grid-----start----

#include<bits/stdc++.h>

using namespace std;



char grid[25][25];
int visit[25][25];
int vis[25][25];

int dc[]={0,0,+1,-1};
int dr[]={+1,-1,0,0};



int rr,cc,q,t;
int cs=1;

void print_graph()
{
    for(int i=0;i<rr;i++)
        {
            for(int j=0;j<cc;j++)
            {
                printf("%c",grid[i][j]);
               // visit[i][j]=0;
            }
            printf("\n");
        }
}

int BFS(int r,int c)
{
    int cnt=1;

    queue< pair<int,int> > q;

    memset(visit,0,sizeof (visit));

    visit[r][c]=1;

    q.push(make_pair(r,c));


    while(!q.empty())
    {
        int a=q.front().first; //row
        int b=q.front().second; //column

        q.pop();

      //  cout<<a<<" "<<grid[a][b]<<" "<<b<<endl;


        for(int k=0;k<4;k++)
        {
            int row=dr[k]+a; //row
            int clm=dc[k]+b; //clm

            if(row>=0 && row<rr && clm>=0 && clm<cc && visit[row][clm]==0 && grid[row][clm]!='#')
            {

                visit[row][clm]=1;
                q.push(make_pair(row,clm));
                cnt++;
            }
        }

    }

    return cnt;



}

int main()
{

   // freopen("input.txt","r",stdin);
    scanf("%d",&t);



    while(t--)
    {
        scanf("%d%d",&cc,&rr);
        int pos_x=0;
        int pos_y=0;

        for(int i=0;i<rr;i++)
        {
            for(int j=0;j<cc;j++)
            {
                scanf(" %c",&grid[i][j]);
                if(grid[i][j]=='@')
                {
                    pos_x=i;
                    pos_y=j;
                }
            }
        }
      // print_graph();

        int z=BFS(pos_x,pos_y);
        printf("Case %d: %d\n",cs,z);
        cs++;


        }



    return 0;

}

BFS_2D_grid-----END----

#DFS(WEIGHT) -----start-----

#include<bits/stdc++.h>

using namespace std;


vector< pair<int,int> > g[30004];
int visit[30004];

int max_cost=0;
int end_point=0;

void dfs(int x,int y)
{
    if(y>max_cost)
    {
        max_cost=y;
        end_point=x;
    }
    //cout<<x<<" and cost :"<<y<<endl;;
    visit[x]=1;
    for(vector< pair<int,int> >::iterator it=g[x].begin();it!=g[x].end();it++)
    {
        //cout<<it->first<<" and "<<it->second<<endl;
        if(visit[it->first]==0)
       dfs(it->first,it->second+y);
    }
}

int main()
{
   // freopen("input.txt","r",stdin);

    int a,b,c,n,t;
    int cs=1;
    cin>>t;

    while(t--)
    {
         cin>>n;

        for(int i=0;i<30004;i++)
        {
            g[i].clear();
        }
        for(int i=0;i<n-1;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            g[a].push_back(make_pair(b,c));
            g[b].push_back(make_pair(a,c));

        }

        max_cost=0;
        memset(visit,0,sizeof visit);
        dfs(0,0);

        max_cost=0;
        memset(visit,0,sizeof visit);
        dfs(end_point,0);

        printf("Case %d: %d\n",cs,max_cost);
        cs++;


    }




    return 0;
}
DFS(Weight)-----END

DFS(normal)------start----
#include<bits/stdc++.h>

#define MAXX 100005

using namespace std;

bool visit[MAXX];

vector <int> edges[MAXX];


int level[MAXX];
int cnt[MAXX];

int res=0;

void DFS(int src)
{
        cout<<src<<endl;
        visit[src]=true;
         int sz = edges[src].size();

        for( int i=0;i<sz; ++i)
        {
            int des=edges[src][i];
            if(visit[des]==false)
            {
		///level korte hole ekhane korte hobe
		DFS(des);
            }
        }


}

int main()
{

    freopen("input.txt","r",stdin);
    int t,cs=1;
    int edge,node;

    cin>>t;

    while(t--)
    {
       scanf("%d",&node);
       edge=node-1;
        int x,y;
        int a,b;

        for(int i=0;i<MAXX;i++)
        {
            edges[i].clear();
            visit[i]=false;
        }

        for(int i=1;i<=edge;++i)
        {
            scanf("%d%d",&x,&y);

            edges[x].push_back(y);
         //   edges[y].push_back(x);
        }
        DFS(1);

        printf("Case %d: %d\n",cs,res);
        cs++;

    }

    return 0;
}

DFS----End------

BFS(bicoloring)----start----
#include<bits/stdc++.h>
#define mxnd 100005
#define ll long long
#define MAX(a,b) ((a>b)?a:b)
using namespace std;

vector<int> edges[mxnd];

int visit[mxnd];
int color[mxnd];
int exist[mxnd];
queue<int> q;
  ll blk=0,wht=0;
void BFS(int a)
{
    visit[a]=1;
    color[a]=1;
    blk++;
    q.push(a);

    while(!q.empty())
    {
        int node=q.front();

        q.pop();

     //   cout<<node<<": clr:"<<color[node]<<endl; ///extra

        int sz=edges[node].size();

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

            if(visit[edges[node][i]]==0 && color[edges[node][i]]==-1)
            {
                color[edges[node][i]]=1-color[node];
                visit[edges[node][i]]=1;
                q.push(edges[node][i]);
                if( color[edges[node][i]]==1) blk++;
                else wht++;
            }
        }


    }

}

int main()
{
  //  freopen("input.txt","r",stdin);
    int n,e;
    int x,y;


        for(int i=0;i<mxnd;i++)
        {
            visit[i]=0;
            color[i]=-1;
        }

        scanf("%d",&n);


        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            edges[x].push_back(y);
            edges[y].push_back(x);
        }

        BFS(1);

        if(blk+wht!=n)
        {
            cout<<"0"<<endl;
            return 0;
        }
        ll res=0;
        for(int i=1;i<=n;i++)
        {
            if(color[i]==1)
            {
               res=res+(abs(wht-edges[i].size()));
             //  cout<<i<<endl;
              // cout<<edges[i].size()<<endl;
            }
        }

    cout<<res<<endl;



    return 0;
}
-----BFS(bicoloring)-----end------

knapsack ----start---

#include <bits/stdc++.h>

#define MAX(a,b) ((a>b)?a:b)
#define MIN(a,b) ((a<b)?a:b)
#define loop(i, a, b) for(int i=(a);i<=(b);i++)

#define pf(x) printf(x);
#define dbg(x) printf("\n--bug: %d --\n",x)
#define PI 2*acos(0.0)
#define all(x) x.begin(),x.end()
#define ll long long
#define pb push_back
#define NL printf("\n")


using namespace std;
struct items{
    int time,des,val,idx;
}a[105];
int n;
int dp[105][2005];
int dir[105][2005];
vector<items> res;
bool cmp(items a,items b)
{
    return a.des<b.des;    ///comparison argument
}

bool cmp_idx(items a,items b)
{
    return a.idx<b.idx;  /// if original sequence is required then
}

int fun(int item,int taken)
{
   //cout<<"working on: "<<item<<"  "<<taken<<endl;
    if(item>=n) return 0;

    if(dp[item][taken]!=-1) return dp[item][taken];

    int profit1=0;
    int profit2=0;

    if((taken+a[item].time) < a[item].des)
    {
        profit1= a[item].val + fun(item+1,taken+a[item].time);
    }
    else profit1=0;

    profit2=fun(item+1,taken);

    dir[item][taken]=(profit1>profit2)?1:2;

    return dp[item][taken]=max(profit1,profit2);
}
void solution_print(int item,int taken)
{

    if(dir[item][taken]==1)
    {
        res.pb(a[item]);
        solution_print(item+1,taken+a[item].time);
    }
    else if(dir[item][taken]==2)
    {
        solution_print(item+1,taken);
    }
}
int main()
{
//	freopen("input.txt","r",stdin);
	 for(int i=0;i<105;i++)
    {
        for(int j=0;j<2005;j++)
        {
            dp[i][j]=-1;
            dir[i][j]=-1;
        }

    }

	cin>>n;
	loop(i,0,n-1)
	{
	    scanf("%d%d%d",&a[i].time,&a[i].des,&a[i].val);
	    a[i].idx=i+1;  /// +1 lagbe indexing 1 theke bujhanor jonno
	}


	sort(a,a+n,cmp);
//    loop(i,0,n-1) cout<<a[i].time<<" "<<a[i].des<<" "<<a[i].val<<endl;
//    NL;
    cout<<fun(0,0)<<endl;

    solution_print(0,0);


  //  sort(all(res),cmp_idx);
    cout<<res.size()<<endl;

    for(int i=0;i<res.size();i++)
    {
        printf("%d ",res[i].idx);
    }
    NL;

	return 0;
}

Knapsack ----end-----
////bool operator<(const pq &x)const{return pw>x.pw;}};             //Min Priority_queue
////priority_queue<int,vi,greater<int> >Q;                          // Min Priority queue for One element.
////int rrr[]={1,0,-1,0};int ccc[]={0,1,0,-1};                      //4 Direction
////int rrr[]={1,1,0,-1,-1,-1,0,1};int ccc[]={0,1,1,1,0,-1,-1,-1};  //8 direction
////int rrr[]={2,1,-1,-2,-2,-1,1,2};int ccc[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
////int rrr[]={2,1,-1,-2,-1,1};int ccc[]={0,1,1,0,-1,-1};           //Hexagonal Direction
////int month[]={31,28,31,30,31,30,31,31,30,31,30,31};              //month