Educoder数据结构实验 图结构试验 第3关：判断有向树

• 任务描述
• 相关知识
• • 实验目的
  • 实验任务
  • 实验说明
  • • 图结构及其类型描述
    • 构建图
• 编程要求
• 测试说明
• 代码展示

本关任务：判断一个有向图是否是一棵有向树。

1. 掌握图的基本概念；
2. 掌握图的存储结构的设计与实现，基本运算的实现；
3. 熟练掌握图的两种遍历算法、遍历生成树及遍历算法的应用。

说明：为使实验程序简洁直观，下面的部分实验程序中的一些功能实现仍以调用库函数程序"graph.h"中的函数的形式给出，并假设该库函数中定义了图结构的类型、结构以及其他一些有关图、边、顶点等的基本操作和函数。

在本头文件中，用自然数表示顶点号。所涉及到的图可以是无向图、有向图、带权图（即网络）等形式。在内部采用邻接表存储，但用户不必关心其具体的存储形式，因为有关的内容可通过头文件中所提供的函数获得。
图结构类型datagraph的描述如下：

struct  datagraph  
{        
   bool direct; //是否是有向的  
   bool flag; //表示这条边是否存在  
};  

为了使同学们不因为复杂的存储结构而分散精力，本实训使用图的邻接矩阵来存储图，也就是datagraph类型的二维数组，datagraph[i][j]表示顶点i到顶点j的边的信息。
如需了解图的邻接表存储结构，推荐一种比较方便的链式前向星存储结构，同学们可以去网上自行查阅相关知识。

请在右侧编辑器的命名空间内填写相关代码，实现判断一个有向图是否是一棵有向树（任意一个顶点可能是根）。
若题目有其它要求，应当将题目要求的结果在solve函数内通过返回或引用的形式传递参数。

数据说明：

• 保证数据给出的图为简单图；
• 保证数据给出的图的顶点数不超过 100；
• G[u][v] 表示的是 u+1 和 v+1 的边。

平台会对你编写的代码进行测试：

函数说明：  
bool solve(vector > & G);  
参数 G 为图的邻接矩阵  
返回一个布尔值表示该图是否为有向树
右侧数据框说明：  
测试输入：  
第一行三个整数 n，m 和 k，n 表示图的顶点总数，m 表示图的边或弧总数，k 表示图是否为有向图，若 k = 1 则表示图为有向图，若 k = 0 则表示图为无向图  
接下来 m 行每行两个整数 u 和 v，表示有一条边或弧 uv 存在  
实际输出：  
输出你返回的布尔值
结构体说明：  
struct  datagraph  
{        
   bool direct; //是否是有向的  
   bool flag; //表示这条边是否存在  
};

库函数详细可查看右侧头文件 "graph.h"  

头文件 “graph.h”

# include 
using namespace std;
namespace exa{

struct  datagraph
{
   bool direct; //是否是有向的
   bool flag; //表示这条边是否存在
};

int solve(vector > & G);

static vector >  load_graph() {
    int n, m, k, u, v;
    cin >> n >> m >> k;
    vector A;
    datagraph a;
    vector > res;
    for (int i = 0; i < n; ++i) {
        res.push_back(A);
        for (int j = 0; j < n; ++j) {
            res[i].push_back(a);
        }
    }
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
        res[i][j].flag = 0;
    }
    for (int i = 1; i <= m; ++i) {
        cin >> u >> v;
        --u; --v;
        if (k == 1) {
            res[u][v].direct = 1;
            res[u][v].flag = 1;
        }
        else {
            res[u][v].direct = res[v][u].direct = 0;
            res[u][v].flag = res[v][u].flag = 1;
        }
    }
    return res;
}


}

开始你的任务吧，祝你成功！

#include "graph.h"   // 引用库函数文件  
namespace exa {     //请在命名空间内编写代码，否则后果自负
int f[105];
int find(int x) {return f[x] < 0 ? x : f[x] = find(f[x]);}  
void union_set(int x, int y) {  
    x = find(x);  
    y = find(y);  
    if (x != y) f[x] += f[y], f[y] = x;  
}
bool solve(vector > & G) {  
    int n = G.size();  
    vector vis(n,0);  
    for (int i = 0; i < n; ++i) f[i] = -1;  
    for (int i = 0; i < n; ++i) {  
        for (int j = 0; j < n; ++j) {  
            if (G[i][j].flag == true) {  
                ++vis[j];  
                union_set(i, j);  
            }  
        }  
    }  
    int zero = 0, one = 0;  
    for (int i = 0; i < n; ++i) {  
        if (vis[i] == 0) ++zero;  
        else if (vis[i] == 1) ++one;  
    }  
    return zero == 1 && one == n-1 && f[find(0)] == -n;  
}
}