3.已知无向图邻接矩阵判断树

左手的ㄟ右手 2022-06-02 09:58 208阅读 0赞

题目：判断一个无向图是否为树。

输入：

第一行为正整数n，代表图中点的个数；

接下来n行，每行有n个数据，每个数据以空格分隔，代表邻接矩阵。

输出：

若为树，输出yes；

否则，输出no。

<table style="width:1615px; margin-bottom:20px; background-color:transparent"> 
 <thead> 
  <tr> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> &nbsp;</th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 测试输入<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" title="关于“测试输入”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“测试输入”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 期待的输出<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" title="关于“期待的输出”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“期待的输出”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 时间限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" title="关于“时间限制”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“时间限制”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 内存限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" title="关于“内存限制”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“内存限制”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 额外进程<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" title="关于“{$a} 个额外进程”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“{$a} 个额外进程”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 测试用例 1</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=66666&amp;test=85755&amp;type=in&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">3↵</span></li> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">0&nbsp;1&nbsp;1↵</span></li> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">1&nbsp;0&nbsp;0↵</span></li> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">1&nbsp;0&nbsp;0↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=66666&amp;test=85755&amp;type=out&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">yes↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 1秒</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 64M</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 0</td> 
  </tr> 
 </tbody> 
</table>

#include<stdio.h>     
    #define N 100     
    int a[N][N]; 
    int vis[N]; 
    int n; 
    int dfs(int x) 
    { 
     if (vis[x]) 
            return 0; 
      vis[x] = 1; 
     
       for (int i = x+1; i < n;i++) 
        if (a[x][i]) 
       if (vis[i]) 
            return 0; 
      else if (!dfs(i)) 
          return 0; 
      return 1; 
    } 
    int main() 
    { 
       //freopen("1.txt", "r",stdin); 
     scanf("%d\n", &n); 
     int i, j; 
      for (i = 0; i<n; i++) 
       for (j = 0; j<n; j++) 
           scanf("%d", &a[i][j]); 
     /*for (k = 0; k<n; k++) 
     for (i = 0; i<n; i++) 
       if (a[k][i]) 
       for (j = 0; j<n; j++) 
       if (a[i][k] && a[k][j]){ 
           a[i][j] = 1; 
       } 
      for (i = 0; i<n; i++) 
       for (j = 0; j<n; j++) 
       { 
          if (a[i][j] + a[j][i] == 0){ 
               printf("no\n"); return 0; 
          } 
      } 
      printf("yes\n");*/ 
     int result = dfs(0); 
       if (result) 
        for (int i = 0; i < n;i++) 
      if (!vis[i]) 
           result = 0; 
        if (result) 
            printf("yes\n"); 
       else 
           printf("no\n"); 
        return 0; 
    }