Online Judge Problem 336: “A Node Too Far” Solution In C++

Problem name: A Node Too Far

Platform: UVA Online Judge

Problem code: p336

Click Here to see the problem statement.

UVA Online Judge p336 A Node Too Far Solution Idea Using BFS:

Guys this is a straight cut BFS problem and really easy.

Take NC first and make the adjacency list.

As the nodes can be any like (1, 5, 100, ….). So, we are using a map to store the values of the nodes and label them from node 1 to the total number of nodes.

Then take the source node and TTL as input say a and b. Then you have to run Breadth First Search every time you take these 2 data as input.

Start BFS on the previously created adjacency list for each source node and check how many nodes can be found whose shortest distance is less than or equal to TTL from the source node.

The rest of the nodes can’t be reached from the source node with the given TTL.

I think you can now do this on your own. So, don’t give up too fast and work your best. Then you can check my code.

My Code For The Solution Of  “A Node Too Far ” Problem Using BFS In C++:

• /* ANTHOR KUMAR DAS
• KUET ECE 2K18*/
• #include<bits/stdc++.h>
• using namespace std;
• #define ll long long
• #define sc(a) scanf(“%d”,&a)
• #define sc1(n) scanf(“%lld”,&n)
• #define tc ll tc; sc1(tc);while(tc–)
• #define sc2(b,c) scanf(“%lld%lld”,&b,&c)
• #define f(a,c,b) for(a=c;a<b;a++)
• #define pb(a) push_back(a)
• #define pf push_front
• #define p(k) printf(“%lldn”,k)
• #define pt printf
• #define en printf(“n”)
• #define br break
• #define dot(m) cout<<fixed<<setprecision(10)<<m<<endl
• #define co continue
• #define sc3(s) scanf(“%s”,&s)
• #define ye cout<<“YES”<<endl
• #define mp(a,b) make_pair(a,b)
• #define mm memset
• #define ss second
• #define ff first
• #define no cout<<“NO”<<endl
• #define valid(x,y,row,col) (x>=1&&x<=row&&y>=1&&y<=col)
• #define pii pair<ll,ll>
• ll fx[]= {0,0,1,-1,1,1,-1,-1};
• ll fy[]= {1,-1,0,0,1,-1,1,-1};
• int main()
• {
•     ll nc,cas=1;
•     while(1)
•     {
•         cin>>nc;
•         if(nc==0)
•         {
•             br;
•         }
•         else
•         {
•             ll a,b,c,k,p,n,m,mn=INT_MAX,mx=INT_MIN,t,j,i,l,z=0;
•             bool ans=true;
•             vector<ll>v[31];
•             map<ll,ll>mp;
•             //making adjacency list
•             f(i,0,nc)
•             {
•                 sc2(a,b);
•                 if(mp.find(a)==mp.end())
•                 {
•                     ++z;
•                     mp[a]=z;
•                 }
•                 if(mp.find(b)==mp.end())
•                 {
•                     ++z;
•                     mp[b]=z;
•                 }
•                 v[mp[a]].pb(mp[b]);
•                 v[mp[b]].pb(mp[a]);
•             }
•             //remember we can say that we have a z-1 number of nodes now
•             while(sc2(k,p))
•             {
•                 if(k==0&&p==0)
•                 {
•                     br;
•                 }
•                 else
•                 {
•                     //now applying bfs with source node k and finding how many nodes can be leveled as <=TTL rest of them are not reachable
•                     ll visited[z+1];
•                     mm(visited,0,sizeof(visited));
•                     ll lev[z+1];
•                     mm(lev,-1,sizeof(lev));
•                     queue<ll>q;
•                     q.push(mp[k]);
•                     visited[mp[k]]=1;
•                     lev[mp[k]]=0;
•                     a=0;
•                     while(q.size()!=0)
•                     {
•                         ll temp=q.front();
•                         q.pop();
•                         if(lev[temp]>=p)//If we are at level greater than our TTL size we don’t have to check anymore
•                         {
•                             br;
•                         }
•                         f(i,0,v[temp].size())
•                         {
•                             if(visited[v[temp][i]]==0)
•                             {
•                                 lev[v[temp][i]]=lev[temp]+1;
•                                 visited[v[temp][i]]=1;
•                                 q.push(v[temp][i]);
•                                 if(lev[v[temp][i]]<=p)//Checking if this node’s shortest distance from source less or equal size of TTL or nor
•                                 {
•                                     a++;// Increasing the number of nodes that can be visited
•                                 }
•                             }
•                         }
•                     }
•                     printf(“Case %lld: “,cas++);
•                     pt(“%lld nodes not reachable from node %lld with TTL = %lld.n”,z-a-1,k,p);
•                 }
•             }
•         }
•     }
•     return 0;
• }