About Me

About Me : I have been working as a Software Engineer for various international companies for four years.Currently, I am working as a full stack Javascript developer in Petronas(Malaysia).

Skills

Skills • Javascript •Typescript •Python •C •Java •ReactJs • Redux • VueJs • NestJs • React Testing Library • Django• PostgreSQL • MySQL • NodeJs • Git • Docker • Jira • Visual Studio Code • Slack

সোমবার, ১৬ মার্চ, ২০১৫

UVA :336-A Node Too Far

#include <bits/stdc++.h>
#define READ freopen("input.txt","r",stdin);
#define WRITE freopen("output.txt","w",stdout);
using namespace std;

void BFS(int a);

map<int,int>color;
map<int,int>cost;
map<int,int>no_of_node;
map<int,int>::iterator it;
vector<int>v[100000];
int row,col;
queue<int>Q;

int x[]= {-1,+0,+1,+0};
int y[]= {+0,-1,+0,+1};

int main()
{
    //READ WRITE
    int edge,cas=0;
    while(scanf("%d",&edge)==1&&edge!=0)
    {
        color.clear();
        cost.clear();
        no_of_node.clear();
        for(int i=0;i<100000;i++) v[i].clear();
        for(int a=0; a<edge; a++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
            no_of_node[x]++;
            no_of_node[y]++;

        }


        int node,dis;
        while(scanf("%d %d",&node,&dis)==2)
        {
            if(node==0&&dis==0) break;
            color.clear();
            cost.clear();
            int c=0;


            BFS(node);

            for( it=cost.begin(); it!=cost.end(); it++)
            {

                if(it->second>dis) c++;
            }
            c+=no_of_node.size()-color.size();
            printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",++cas,c,node,dis);

        }


    }

    return 0;
}

void BFS(int root)
{
    color[root]=1;
    cost[root]=0;
    Q.push(root);
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for(int i=0; i<v[u].size(); i++)
        {
            int num=v[u][i];
            if(color[num]==0)
            {

                cost[num]=cost[u]+1;
                color[num]=1;
                Q.push(num);
            }

        }

    }

}


কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন