算法描述:
即判断该无向图不存在环,并且该图是连通的(排除森林的可能性)
int const N = 100;
bool visit[N];// 标记该节点是否访问过
bool edge[N][N];// 数组记录两点是否存在边
int n;// 图中节点的数目
bool dfs(int x,int fa)
{
if(visit[x])return false;
visit[x] = true;
for(int i=1;i<=n;i++)
if(i!=fa&&edge[x][i])
{
if(dfs(i) == false)return false;
}
return true;
}
int main()
{
// 前面嵌套图的输入
int c=0;
bool flag = true;
memset(visit,false,sizeof(visit));
for(int i=1;i<=n;i++)
if(!visit[i])
{
c++;
if(c==2)break;
flag = dfs(i);
if(flag == false)break;
}
if(flag == flag || c==2)puts("不是树");
else puts("是一颗树");
return 0;
}