Graph Algorithms problem (C++) sample output: Tippy is a cute rabbit. He has m f

Question

Graph Algorithms problem (C++)

sample output:

Tippy is a cute rabbit. He has m friends living in ltomori town. Each of his friends lives in exactly one house in Itomori, numbered from 1 to m. There are one-way (i.e., directional) roads connecting these houses. Note that there could be multiple roads connecting two houses One day, Tippy wants to visit his friends in ltomori. He plans to stay at one of his friend's house and isits other friends whose houses are reachable from where he stays. Now the problem is, which house should he stay so that he can visit as many triends as possible while satiSTying the Tollowing rules Tippy moves according to the following rules After his visit, he must come back to the house he stays Tippy has different moving behaviors depending on his mood. When he is happy, he will move backward, otherwise he will move forward. That is, if there exists a road from house Ato house B, then he can move forward from house A to house B when he is in the normal mood, and he can move backward from Bto A when he is happy. There are some special shops (e.g., the comet souvenir shop) on special roads. When Tippy passes by these shops, his mood will change. That is, if he was happy, then he will become normal. If he was normal, then he will become happy. His mood will not change otherwise Tippy is happy when he starts to visit his friends, and he hopes that he will still be happy when coming back. (If the last road is special, he should have normal mood before entering this road.) Input Format The first line contains two integers n, ma, indicating the number of houses and roads in the town. In the next mlines, each line contains 3 integers a, b, S, indicating this road is from house a to house b If s 1, the road is special; otherwise it is a normal road 1 n 10000 1 m 100000 s E 0,1 Test group O (O points) Sample testcases Test group 1 (20 points) n 650, m 800 Test group 2 (30 points) n S 3000, m. S 8000 Test group 3 (50 points) No additional constraints. Output Format Output exactly nlines. In the i-th line exactly one integer, indicating the number of friends he could visit, when he start his visit from house number i

Explanation / Answer

#include<iostream.h>
#include<conio.h>
class road{
   public:
   int a,b,s;//a is house1 and b is house 2 and s is the status of road;
};
void main(){
   int n,m,a,b,s,i=0,j=0,v=0;
   int **adjMatrix;
   clrscr();

   cout<<" Enter Number of Houses:";
   cin>>n;

   if(n<1 ||a>10000){
           cout<<" n value out of reange please Re-Enter n value:";
           cin>>n;

   }

   cout<<"Enter Number of roads:";
   cin>>m;
   if(m<1 ||m>10000){
           cout<<" m value out of reange please Re-Enter m value:";
           cin>>m;

   }

   road* roads=new road[m];
   road r;
   adjMatrix=new int*[n];
   for(i=0;i<m;i++){
       cout<<" Enter a value:";
       cin>>a;

       cout<<" Enter b value:";
       cin>>b;
       cout<<" Ener s value:";
       cin>>s;
       adjMatrix[a-1][b-1]=1;
       r.a=a;
   r.b=b;
       r.s=s;
       roads[i]=r;

   }

   for(i=0;i<n;i++){
       v=0;
       for(j=0;j<m;j++)
       {
           if(roads[j].s==0){
               a=roads[j].a;
               b=roads[j].b;
               if(adjMatrix[a-1][b-1]==1) v++;

           }
       }
          
       cout<<" from house"<<i+1<<"rabit visited "<<v<<"friends";
      
   }}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.