主页 / 问题 / 1533826
Accepted
user504877
Asked:2023-08-02 23:03:14 +0000 UTC2023-08-02 23:03:14 +0000 UTC

使用 ++ 或 python 帮助完成图形任务

  • 772

构造一些包含 K 个连通分量的 N 个顶点的无向图。

例子

输入

5 2

结论

0 0 0 0 1
0 0 1 1 0
0 1 0 1 0
0 1 1 0 0
1 0 0 0 0

规格 输入 给定两个数字 N 和 K，写在一行中（均少于一百）。

输出 导出该图的邻接矩阵（它必须相对于主对角线对称，零必须位于主对角线上）。

请告诉我如何解决这个问题，我在这里没有看到任何 DFS、BFS（只是文本或代码）

python

3 个回答

  1. Best Answer

    抱紧我七！

    N个顶点的完整图中有 N(N - 1)/2条边。让我们收集列表中的边。该列表是随机打乱的。

    对于固定的M ，我们从列表M中选择第一条边。让我们用它们组成一个图并估计其连接分量C M的数量。

    很容易看出C M不随M增加。通过二分查找，我们将找到这样的M，即C M = K。

    问题解决了。复杂度O(N 2 logN)。可以生成任何可能的具有K 个连通分量的N顶点图。

    PS对于不相交集合的系统，问题可以在O(N 2 )中解决，无需对数。什么看起来是最佳时间。

    • 2

  2. “任何”图都很容易生成 - 将顶点分为 K 组，通过将顶点连接成链来确保每组中的连通性，并为该组中的顶点绘制更多边。

    为了使图形不那么无聊，可以在分组之前对顶点进行随机洗牌。

    • 1

  3. 在这里，没有痛苦（来自评论的想法）：

    int n, k;
cin >> n >> k;
for(int i = 0; i < n; ++i)
{
    for(int j = 0; j < n; ++j)
        cout << (i >= k-1 && j >= k-1 && i != j) << " ";
    cout << "\n";
}

    自己检查一下n >= k...

    • 1

相关问题