文章

47

粉丝

317

获赞

54

访问

28.8k

头像
P1566 确定比赛名次 答疑提问:求助,不知道哪点有问题
fzh VIP
P1566 中山大学2019年机试题
发布于2025年3月11日 23:52
阅读数 42

#include
using namespace std;
struct TNode
{
    int data;
    TNode* rchild, * lchild;

};

void Insert(TNode*& root, int x)
{
    if (!root)
    {
        root = new TNode;
        root->data = x;
        root->rchild = NULL;
        root->lchild = NULL;
        return;
    }
    if (x > root->data) Insert(root->rchild,  x);
    if (x < root->data) Insert(root->lchild,  x);
}

void Pre(TNode* root)
{
    if (!root) return;
    cout << root->data << ' ';
    Pre(root->lchild);
    Pre(root->rchild);
}
void Mid(TNode* root)
{
    if (!root) return;

 &...

登录查看完整内容


登录后发布评论

2 条评论
admin SVIP
2025年3月12日 11:53

看了这道题的最后一次提交,通过50%的代码。

冗余换行符导致格式错误
在每组数据处理结束后,无论是否已正确换行,都会额外输出一个换行符。例如,当处理最后一个元素时,num == n 会输出 '\n',但循环结束后又执行 cout << endl;,导致每组输出后多出一个空行。这会使得实际输出比题目要求多出一行空白。

邻接矩阵遍历效率低下
使用邻接矩阵遍历所有节点(O(N) 复杂度)来查找邻接点,而实际上只需遍历存在的边。对于稀疏图(M << N²),这会显著降低效率。建议改用邻接表存储图结构。

修正后的代码:
 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<vector<int>> graph(n); // 邻接表存储
        vector<int> indegree(n, 0);
        
        for (int i = 0; i < m; ++i) {
            int p1, p2;
            cin >> p1 >> p2;
            graph[p1-1].push_back(p2-1); // 存储邻接节点索引
            indegree[p2-1]++;
        }
        
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int i = 0; i < n; ++i) {
            if (indegree[i] == 0) pq.push(i);
        }
        
        int cnt = 0;
        while (!pq.empty()) {
            int u = pq.top();
            pq.pop();
            cout << u + 1 << (++cnt == n ? "\n" : " "); // 直接控制末尾空格
            for (int v : graph[u]) { // 仅遍历实际邻接节点
                if (--indegree[v] == 0) {
                    pq.push(v);
                }
            }
        }
    }
    return 0;
}

 

赞(1)

fzh : 回复 admin: 谢谢佬!

2025年3月12日 13:01