fork download
copy 
  1. #include<iostream>
  2.  
  3. #define N 100
  4.  
  5.  
  6.  
  7. using namespace std;
  8.  
  9.  
  10.  
  11.  
  12.  
  13. struct Node{
  14.  
  15.  
  16.  
  17.      int data;   
  18.  
  19.      Node *link;
  20.  
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.         };
  28.  
  29.  
  30.  
  31. struct stack{
  32.  
  33.        Node* stackarray[N];
  34.  
  35.        int sp;
  36.  
  37.  
  38.  
  39.  
  40.  
  41.        };
  42.  
  43.  
  44.  
  45. stack s;        
  46.  
  47.  
  48.  
  49.  
  50.  
  51. struct Queue{
  52.  
  53.         Node* queuearray[N];
  54.  
  55.         int rear;
  56.  
  57.         int front;              
  58.  
  59.         };
  60.  
  61.  
  62.  
  63. Queue q;
  64.  
  65.  
  66.  
  67. Node Adjlist[9];
  68.  
  69. bool visited[9];
  70.  
  71. bool predecessor[9];
  72.  
  73. int mark[9];
  74.  
  75. bool flag=true;
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85. void construct(Node*,int);
  86.  
  87.  
  88.  
  89. int push(stack *,Node*&);
  90.  
  91. void pop(stack *,Node*&);
  92.  
  93. int isempty(stack *);
  94.  
  95. int isfull(stack *);
  96.  
  97. void visit(Node*);
  98.  
  99. void DFS(Node*);
  100.  
  101. void BFS(Node *);
  102.  
  103. void createQueue(Queue *);
  104.  
  105. void queueMove(Queue *);
  106.  
  107. int isEmpty(Queue *);
  108.  
  109. void enQueue(Queue *,Node*&);
  110.  
  111. void deQueue(Queue *,Node*&);
  112.  
  113. void addEdge(Node *,Node *);
  114.  
  115. void checkConnectedDirection();
  116.  
  117. void checkBipart(Node *);
  118.  
  119. void checkConnectedUndirection(Node *);
  120.  
  121. void componentCount();
  122.  
  123. void checkCycleUndirection(Node *);
  124.  
  125. void checkCycleDirection(Node *);
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133. int main(void){
  134.  
  135.  
  136.  
  137.  
  138.  
  139.      for(int i=1;i<=8;i++){
  140.  
  141.       Adjlist[i].link=NULL;
  142.  
  143.       Adjlist[i].data=i;}
  144.  
  145.  
  146.  
  147.     Node *head1=&Adjlist[1];
  148.  
  149.     Node *head2=&Adjlist[2];
  150.  
  151.     Node *head3=&Adjlist[3];
  152.  
  153.     Node *head4=&Adjlist[4];
  154.  
  155.     Node *head5=&Adjlist[5];
  156.  
  157.     Node *head6=&Adjlist[6];
  158.  
  159.     Node *head7=&Adjlist[7];
  160.  
  161.     Node *head8=&Adjlist[8];
  162.  
  163.  
  164.  
  165.  
  166.  
  167.    construct(head1,2);
  168.  
  169.     construct(head1,4);
  170.  
  171.  
  172.  
  173.     construct(head2,3);
  174.  
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.     construct(head3,6);
  182.  
  183.  
  184.  
  185.     construct(head4,5);
  186.  
  187.     construct(head5,6);
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.      createQueue(&q);
  198.  
  199.      s.sp=-1;
  200.  
  201.  
  202.  
  203.      for(int i=1;i<=8;i++)  
  204.  
  205.       visited[i]=false;
  206.  
  207.  
  208.  
  209.  
  210.  
  211.  
  212.  
  213.       checkCycleDirection(head1);
  214.  
  215.     //checkConnectedUndirection(head7);
  216.  
  217.      //DFS(head3);
  218.  
  219.  
  220.  
  221.    // componentCount(head4);
  222.  
  223.  
  224.  
  225.    //checkBipart(head1);
  226.  
  227.  
  228.  
  229.  
  230.  
  231.     system("pause");
  232.  
  233.     return 0;
  234.  
  235. }
  236.  
  237.  
  238.  
  239. void construct(Node* ptr,int x){
  240.  
  241.       Node *ppp=new Node;
  242.  
  243.       ppp->data=x;
  244.  
  245.       ppp->link=NULL;
  246.  
  247.  
  248.  
  249.       while(ptr->link!=NULL){
  250.  
  251.  
  252.  
  253.         ptr=ptr->link;
  254.  
  255.  
  256.  
  257.      }
  258.  
  259.      ptr->link=ppp;
  260.  
  261.  
  262.  
  263.      }
  264.  
  265.  
  266.  
  267.  
  268.  
  269.  
  270.  
  271.  
  272.  
  273.  
  274.  
  275.  
  276.  
  277. void Mix(Node *ptr){
  278.  
  279.       int count=1;
  280.  
  281.       Node *Vx,*Vy;
  282.  
  283.       int before;
  284.  
  285.       bool tag=false;
  286.  
  287.       bool bitag=false;
  288.  
  289.       push(&s,ptr);
  290.  
  291.       while(!(isempty(&s))){
  292.  
  293.  
  294.  
  295.            pop(&s,Vx); 
  296.  
  297.  
  298.  
  299.         if(visited[Vx->data]==false){
  300.  
  301.             cout<<"Visit:"<<Vx->data<<endl;
  302.  
  303.             visited[Vx->data]=true;
  304.  
  305.              mark[Vx->data]=(count++)%2;
  306.  
  307.  
  308.  
  309.  
  310.  
  311.              Vy=Adjlist[Vx->data].link;
  312.  
  313.  
  314.  
  315.              while(Vy!=NULL){
  316.  
  317.  
  318.  
  319.                     if(mark[Vy->data]==mark[Vx->data]&&bitag==false){
  320.  
  321.                       cout<<"不是二分圖!!"<<endl;       
  322.  
  323.                       bitag=true;       
  324.  
  325.                              }
  326.  
  327.                     if(visited[Vy->data]==false){                    
  328.  
  329.                     push(&s,Vy);}
  330.  
  331.                     else{
  332.  
  333.                       if(Vy->data!=before&&tag==false){
  334.  
  335.                       cout<<"發現迴圈!!"<<endl;   
  336.  
  337.                       tag=true;
  338.  
  339.                       }
  340.  
  341.                          }
  342.  
  343.                     Vy=Vy->link;          
  344.  
  345.                                  }
  346.  
  347.  
  348.  
  349.  
  350.  
  351.                 before=Vx->data;
  352.  
  353.  
  354.  
  355.                                  }
  356.  
  357.  
  358.  
  359.  
  360.  
  361.                                }                  
  362.  
  363.  
  364.  
  365.  
  366.  
  367.  
  368.  
  369.                           }
  370.  
  371.  
  372.  
  373.  
  374.  
  375. void DFS(Node *ptr){
  376.  
  377.  
  378.  
  379.       for(int i=1;i<=8;i++)  
  380.  
  381.        visited[i]=false;
  382.  
  383.  
  384.  
  385.  
  386.  
  387.       Node *Vx,*Vy;
  388.  
  389.  
  390.  
  391.  
  392.  
  393.       push(&s,ptr);
  394.  
  395.       while(!(isempty(&s))){
  396.  
  397.  
  398.  
  399.            pop(&s,Vx); 
  400.  
  401.  
  402.  
  403.         if(visited[Vx->data]==false){
  404.  
  405.  
  406.  
  407.             cout<<"Visit:"<<Vx->data<<endl;
  408.  
  409.             visited[Vx->data]=true;
  410.  
  411.  
  412.  
  413.  
  414.  
  415.  
  416.  
  417.              Vy=Adjlist[Vx->data].link;
  418.  
  419.  
  420.  
  421.              while(Vy!=NULL){
  422.  
  423.  
  424.  
  425.  
  426.  
  427.                     if(visited[Vy->data]==false)                   
  428.  
  429.                     push(&s,Vy);
  430.  
  431.  
  432.  
  433.  
  434.  
  435.                     Vy=Vy->link;          
  436.  
  437.                                  }
  438.  
  439.  
  440.  
  441.                                  }
  442.  
  443.  
  444.  
  445.  
  446.  
  447.                                }                  
  448.  
  449.  
  450.  
  451.  
  452.  
  453.                           }
  454.  
  455.  
  456.  
  457.  
  458.  
  459.  
  460.  
  461. void BFS(Node *ptr){
  462.  
  463.      Node *Vx,*Vy;
  464.  
  465.       cout<<"Visit:"<<ptr->data<<endl;
  466.  
  467.       visited[ptr->data]=true;
  468.  
  469.      enQueue(&q,ptr);
  470.  
  471.  
  472.  
  473.      while(!isEmpty(&q)){
  474.  
  475.             deQueue(&q,Vx);
  476.  
  477.  
  478.  
  479.               Vy=Adjlist[Vx->data].link;
  480.  
  481.  
  482.  
  483.             while(Vy!=NULL){
  484.  
  485.  
  486.  
  487.                     if(visited[Vy->data]==false){
  488.  
  489.                     cout<<"Visit:"<<Vy->data<<endl;
  490.  
  491.                     visited[Vy->data]=true;
  492.  
  493.                     cout<<"加入邊:("<<Vx->data<<","<<Vy->data<<")"<<endl;
  494.  
  495.                     enQueue(&q,Vy);}
  496.  
  497.  
  498.  
  499.                     Vy=Vy->link;          
  500.  
  501.                                  }                    
  502.  
  503.                        } 
  504.  
  505.      }
  506.  
  507.  
  508.  
  509.  
  510.  
  511.  
  512.  
  513. void addEdge(Node *x,Node *y){
  514.  
  515.      cout<<"加入邊:("<<x->data<<","<<y->data<<")"<<endl;
  516.  
  517.  
  518.  
  519.  
  520.  
  521.  
  522.  
  523.      }     
  524.  
  525.  
  526.  
  527.  
  528.  
  529.  
  530.  
  531.  
  532.  
  533.  
  534.  
  535. void visit(Node *x){
  536.  
  537.  
  538.  
  539.       visited[x->data]=true;
  540.  
  541.       cout<<"Visit Vertex:"<<x->data<<" "<<endl;
  542.  
  543.  
  544.  
  545.      }
  546.  
  547.  
  548.  
  549.  
  550.  
  551.  
  552.  
  553.  
  554.  
  555. int push(stack *p,Node* &x){
  556.  
  557.      if(isfull(p))
  558.  
  559.      return 1;
  560.  
  561.      p->sp++;
  562.  
  563.      p->stackarray[p->sp]=x;
  564.  
  565.  
  566.  
  567.      }
  568.  
  569.  
  570.  
  571. void pop(stack *p,Node *&x){
  572.  
  573.  
  574.  
  575.      x=p->stackarray[p->sp--];     
  576.  
  577.  
  578.  
  579.  
  580.  
  581.      } 
  582.  
  583.  
  584.  
  585. int isempty(stack *p){
  586.  
  587.      if(p->sp==-1)
  588.  
  589.      return 1;
  590.  
  591.      else
  592.  
  593.      return 0;      
  594.  
  595.      }
  596.  
  597.  
  598.  
  599. int isfull(stack *p){
  600.  
  601.     if(p->sp==N-1)   
  602.  
  603.     return 1;
  604.  
  605.     else
  606.  
  607.     return 0;   
  608.  
  609. }
  610.  
  611.  
  612.  
  613.  
  614.  
  615.  
  616.  
  617.  
  618.  
  619. void createQueue(Queue *p){
  620.  
  621.      p->rear=-1;
  622.  
  623.      p->front=-1;
  624.  
  625.      }
  626.  
  627.  
  628.  
  629.  
  630.  
  631. void enQueue(Queue *p,Node* &x){
  632.  
  633.     if(p->rear==N-1)
  634.  
  635.      queueMove(p);
  636.  
  637.  
  638.  
  639.  
  640.  
  641.      p->rear++;
  642.  
  643.      p->queuearray[p->rear]=x;
  644.  
  645.  
  646.  
  647.  
  648.  
  649.  
  650.  
  651.      }
  652.  
  653. void deQueue(Queue *p,Node* &x){
  654.  
  655.  p->front++;
  656.  
  657.  x=p->queuearray[p->front];
  658.  
  659.  
  660.  
  661.  
  662.  
  663. }
  664.  
  665.  
  666.  
  667. void queueMove(Queue *p){
  668.  
  669.      int i;
  670.  
  671.      for(i=p->front+1;i<=p->rear;i++)
  672.  
  673.      p->queuearray[i-p->front-1]=p->queuearray[i];
  674.  
  675.      p->rear=p->rear-p->front-1;
  676.  
  677.      p->front=-1;
  678.  
  679.  
  680.  
  681.      }
  682.  
  683.  
  684.  
  685. int isEmpty(Queue *p){
  686.  
  687.     if(p->rear==p->front)
  688.  
  689.     return 1;
  690.  
  691.     else
  692.  
  693.     return 0;
  694.  
  695.     }
  696.  
  697.  
  698.  
  699.  
  700.  
  701. void checkConnectedDirection(){
  702.  
  703.  
  704.  
  705.      bool tag=true;
  706.  
  707.  
  708.  
  709.      for(int i=1;i<=8;i++)
  710.  
  711.        visited[i]=false;
  712.  
  713.  
  714.  
  715.      for(int i=1;i<=8;i++){
  716.  
  717.  
  718.  
  719.         DFS(&Adjlist[i]);
  720.  
  721.  
  722.  
  723.         for(int i=1;i<=8;i++){
  724.  
  725.            if(visited[i]==false){
  726.  
  727.                 tag=false;
  728.  
  729.                 goto L1;
  730.  
  731.                 }
  732.  
  733.                 }
  734.  
  735.  
  736.  
  737.          for(int i=1;i<=8;i++)
  738.  
  739.            visited[i]=false;        
  740.  
  741.  
  742.  
  743.  
  744.  
  745.      }
  746.  
  747.  
  748.  
  749.      L1:
  750.  
  751.           if(tag==false)
  752.  
  753.            cout<<"此有向圖形不是connected"<<endl;
  754.  
  755.            else
  756.  
  757.            cout<<"此有向圖形是connected"<<endl;     
  758.  
  759.  
  760.  
  761.  
  762.  
  763.      }
  764.  
  765.  
  766.  
  767.  
  768.  
  769. void checkConnectedUndirection(Node *ptr){
  770.  
  771.  
  772.  
  773.  
  774.  
  775.         bool tag=true;
  776.  
  777.  
  778.  
  779.      for(int i=1;i<=8;i++)
  780.  
  781.        visited[i]=false;
  782.  
  783.  
  784.  
  785.         DFS(ptr);
  786.  
  787.  
  788.  
  789.         for(int i=1;i<=8;i++){
  790.  
  791.            if(visited[i]==false){ 
  792.  
  793.                 tag=false;
  794.  
  795.                 break;
  796.  
  797.                 }                                              
  798.  
  799.              }     
  800.  
  801.  
  802.  
  803.            if(tag==false)
  804.  
  805.               cout<<"此無向圖形不是connected"<<endl;
  806.  
  807.            else
  808.  
  809.               cout<<"此無向圖形是connected"<<endl;  
  810.  
  811.  
  812.  
  813.  
  814.  
  815.  
  816.  
  817.  
  818.  
  819.      }
  820.  
  821.  
  822.  
  823.  
  824.  
  825.  
  826.  
  827.  
  828.  
  829. void componentCount(){
  830.  
  831.  
  832.  
  833.        int count=0;
  834.  
  835.        for(int i=1;i<=8;i++)
  836.  
  837.           visited[i]=false;
  838.  
  839.  
  840.  
  841.        for(int i=1;i<=8;i++){
  842.  
  843.  
  844.  
  845.                if(visited[i]==false){
  846.  
  847.                  DFS(&Adjlist[i]);
  848.  
  849.                count++;
  850.  
  851.                }
  852.  
  853.  
  854.  
  855.  
  856.  
  857.                }  
  858.  
  859.  
  860.  
  861.          cout<<"此圖形的連通組件有"<<count<<"個"<<endl;       
  862.  
  863.  
  864.  
  865.     }
  866.  
  867.  
  868.  
  869.  
  870.  
  871. void checkBipart(Node *ptr){
  872.  
  873.  
  874.  
  875.       int count=1;
  876.  
  877.       Node *Vx,*Vy;
  878.  
  879.       bool bitag=false;
  880.  
  881.  
  882.  
  883.        for(int i=1;i<=8;i++)  
  884.  
  885.         mark[i]=2;
  886.  
  887.  
  888.  
  889.       push(&s,ptr);
  890.  
  891.       while(!(isempty(&s))){
  892.  
  893.  
  894.  
  895.            pop(&s,Vx); 
  896.  
  897.  
  898.  
  899.         if(visited[Vx->data]==false){
  900.  
  901.             cout<<"Visit:"<<Vx->data<<endl;
  902.  
  903.             visited[Vx->data]=true;
  904.  
  905.  
  906.  
  907.              mark[Vx->data]=(count++)%2;
  908.  
  909.  
  910.  
  911.  
  912.  
  913.              Vy=Adjlist[Vx->data].link;
  914.  
  915.  
  916.  
  917.              while(Vy!=NULL){
  918.  
  919.  
  920.  
  921.                     if(mark[Vy->data]==mark[Vx->data]&&bitag==false){
  922.  
  923.                       cout<<"不是二分圖!!"<<endl;       
  924.  
  925.                       bitag=true;       
  926.  
  927.                              }
  928.  
  929.                     if(visited[Vy->data]==false)                 
  930.  
  931.                     push(&s,Vy);
  932.  
  933.  
  934.  
  935.  
  936.  
  937.                     Vy=Vy->link;          
  938.  
  939.                                  }
  940.  
  941.  
  942.  
  943.                                  }
  944.  
  945.  
  946.  
  947.                                }  
  948.  
  949.             if(bitag==false)
  950.  
  951.           cout<<"是二分圖!!!"<<endl;                       
  952.  
  953.  
  954.  
  955.      }
  956.  
  957.  
  958.  
  959.  
  960.  
  961.  
  962.  
  963. void checkCycleUndirection(Node *ptr){
  964.  
  965.  
  966.  
  967.  
  968.  
  969.       Node *Vx,*Vy;
  970.  
  971.  
  972.  
  973.       bool tag=false;
  974.  
  975.  
  976.  
  977.       push(&s,ptr);
  978.  
  979.  
  980.  
  981.       while(!(isempty(&s))){
  982.  
  983.  
  984.  
  985.            pop(&s,Vx); 
  986.  
  987.  
  988.  
  989.         if(visited[Vx->data]==false){
  990.  
  991.             cout<<"Visit:"<<Vx->data<<endl;
  992.  
  993.             visited[Vx->data]=true;
  994.  
  995.  
  996.  
  997.  
  998.  
  999.  
  1000.  
  1001.              Vy=Adjlist[Vx->data].link;
  1002.  
  1003.  
  1004.  
  1005.              while(Vy!=NULL){
  1006.  
  1007.  
  1008.  
  1009.  
  1010.  
  1011.                     if(visited[Vy->data]==false){                    
  1012.  
  1013.                     push(&s,Vy);}
  1014.  
  1015.                     else{
  1016.  
  1017.                       if(visited[Vy->data]==true&&tag==false){
  1018.  
  1019.                       cout<<"發現迴圈!!"<<endl;   
  1020.  
  1021.                       tag=true;
  1022.  
  1023.                       }
  1024.  
  1025.                          }
  1026.  
  1027.                     Vy=Vy->link;          
  1028.  
  1029.                                  }
  1030.  
  1031.  
  1032.  
  1033.  
  1034.  
  1035.  
  1036.  
  1037.  
  1038.  
  1039.                                  }
  1040.  
  1041.  
  1042.  
  1043.  
  1044.  
  1045.                                }                  
  1046.  
  1047.      }
  1048.  
  1049.  
  1050.  
  1051.  
  1052.  
  1053. void checkCycleDirection(Node *ptr){
  1054.  
  1055.  
  1056.  
  1057.  
  1058.  
  1059.       Node *Vx,*Vy;
  1060.  
  1061.  
  1062.  
  1063.       bool tag=false;
  1064.  
  1065.  
  1066.  
  1067.       push(&s,ptr);
  1068.  
  1069.  
  1070.  
  1071.       while(!(isempty(&s))){
  1072.  
  1073.  
  1074.  
  1075.            pop(&s,Vx); 
  1076.  
  1077.  
  1078.  
  1079.         if(visited[Vx->data]==false){
  1080.  
  1081.             cout<<"Visit:"<<Vx->data<<endl;
  1082.  
  1083.             visited[Vx->data]=true;
  1084.  
  1085.             predecessor[Vx->data]=true;
  1086.  
  1087.  
  1088.  
  1089.  
  1090.  
  1091.              Vy=Adjlist[Vx->data].link;
  1092.  
  1093.                if(Vy==NULL)
  1094.  
  1095.               predecessor[Vx->data]=false;
  1096.  
  1097.  
  1098.  
  1099.              while(Vy!=NULL){
  1100.  
  1101.  
  1102.  
  1103.  
  1104.  
  1105.                     if(visited[Vy->data]==false){                    
  1106.  
  1107.                     push(&s,Vy);}
  1108.  
  1109.                     else{
  1110.  
  1111.                       if(predecessor[Vy->data]==true&&tag==false){
  1112.  
  1113.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:231: error: ‘system’ was not declared in this scope
prog.cpp:157: warning: unused variable ‘head6’
prog.cpp:159: warning: unused variable ‘head7’
prog.cpp:161: warning: unused variable ‘head8’
prog.cpp: In function ‘void checkCycleDirection(Node*)’:
prog.cpp:1111: error: expected `}' at end of input
prog.cpp:1111: error: expected `}' at end of input
prog.cpp:1111: error: expected `}' at end of input
prog.cpp:1111: error: expected `}' at end of input
prog.cpp:1111: error: expected `}' at end of input
prog.cpp:1111: error: expected `}' at end of input
stdout
copy 
Standard output is empty
https://ideone.com/x31jcG
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!