首页 > 试题广场 >

已知如下递归代码用于求解图的m着色问题：#define N&

[单选题]
已知如下递归代码用于求解图的m着色问题：
#define N 10 
int a[N+1][N+1]; //存储图
int x[N+1];//记录颜色
int sum=0;//保存可着色方案数

void backtrace(int t,int m)
{
int i;
if(t>N)//搜索至叶节点 
{
sum++;
printf("第%d种方案：\n",sum);
for(i=1;i<=N;i++)
printf("%d ",x[i]);
printf("\n");
}
else
{
for(i=1;i<=m;i++) //逐个判断每种颜色 
{
if(check(t,i))
{   x[t]=i;
backtrace(t+1,m);
}
}
}
}


其中check()函数用于检测某个节点颜色是否合法，以下check()函数正确的是：
  • int check(int t,int i)//检测函数 {     int j;     for(j=1;j&lt;t;j++)     {         if(a[t][j]==1&amp;&amp;x[i]==j)                  return 0;            }     return 1; }
  • int check(int t,int i)//检测函数 {     int j;     for(j=1;j&lt;t;j++)     {         if(a[t][j]==1||x[i]==j)                  return 0;            }     return 1; }
  • int check(int t,int i)//检测函数 {     int j;     for(j=1;j&lt;t;j++)     {         if(a[t][j]==1||x[j]==i)                  return 0;            }     return 1; }
  • int check(int t,int i)//检测函数 {     int j;     for(j=1;j&lt;t;j++)     {         if(a[t][j]==1&amp;&amp;x[j]==i)                  return 0;            }     return 1; }
查看答案及解析
添加回答
我的天鸭头像 我的天鸭 
int check(int t,int i){     
    int j;     
    for(j=1;j<t;j++){    //遍历已经涂色过的所有节点         
        if(a[t][j]==1&&x[j]==i)    //当前节点t与已涂色过的节点j有边相连并且颜色与t颜色相同,返回无效,需要增加颜色
            return 0;            
    }     
    return 1; 
}

发表于 2019-08-21 11:45:11 回复(0)
腹黑gg头像 腹黑gg 
//当t跟j是相邻并且j已经等于i，那么t就不可以等于i了
for(j = 1;j<t;j++)
{
    if(a[t][j] == 1&&x[j] == i)
        return 0;
}
 
 

                                                                                    



                                        

                                            
                                                                                                                                                            发表于  2018-12-18 23:10:40
                                                    
                                                                                            
                                                回复(0)
                                                                                                                                            

                                        

                                


                                                                                                                            
                                                                

                                


                                    

                                                                                
                                        
                                        
                                                                            


                                    


                                        

                                                                                                                                    午睡到凌晨头像
                                            午睡到凌晨
                                        



                                        

                                                                                            求大佬解读代码
                                                                                    



                                        

                                            
                                                                                                                                                            发表于  2019-10-28 23:26:57
                                                    
                                                                                            
                                                回复(0)
                                                                                                                                            

                                        

                                


                                                            
                        

                        
                                        

                            

        


                    

                                    

                        

                            

                            

                                提交观点
                            

                        

                    

                            

            

    

          

            
问题信息

            

              

                                      C++工程师
                                      2018
                                      C++
                                      360集团
                                

                                  

                    来自：360公司-2018春...
                  

                
                                                      

                          上传者：小小
                      

                                              

                                        难度：

                                

                                        3条回答
                      
                      1896浏览
                                

            

          

            




















                    

            

                        

  

    

      
      
      
    

    
热门推荐

  

  

    

      
    

  



            

                

            

          
                        

                          

                
相关试题

                

                  
                

              

                





                
        

                                                                

        

    
    
    

    


            
    
    

        

            

                
            

            
扫一扫，把题目装进口袋

        

        

            
求职之前，先上牛客

            

                
                    

                        

                        

                            
                            
扫描二维码，进入QQ群

                        

                    

                
                
                    

                        

                        

                            
                            
扫描二维码，关注牛客公众号