论坛 › C\C++交流 › C:Runtime Error.

风眠 发表于 5 天前

C:Runtime Error.

题目：https://www.luogu.com.cn/problem/P8655

代码：
#include <stdio.h>


int main()
{
        int N;
        scanf("%d",&N);

        int link;
        int ans;
        int a,b;
        int index;

        for(int i = 0;i < N+1;i++)
        {
                for(int j = 0;j < N+1;j++)
                {
                        link = 0;
                }
                ans = 0;
        }
        for (int i = 0;i < N;i++)
        {
                scanf("%d %d",&a,&b);
                ans++;
                ans++;
                link = 1;
                link = 1;
        }

       
        for (int i = 1;i < N+1;i++)
        {
                if (ans == 1)
                {
                        index = i;
                        cut:
                        ans--;
                        for (int j = 0;j < N;j++)
                        {
                                if (link == 1)
                                {
                                        ans--;
                                        link = 0;
                                        link = 0;
                                        if (ans == 1)
                                        {
                                                index = j;
                                                goto cut;
                                        }
                                }
                        }

                }
        }


        for(int i = 1;i < N+1;i++)
        {
                if (ans != 0)
                {
                        printf("%d ",i);
                }
        }
        //printf("\b\n");
       

       

        return 0;
}

问题：
Runtime Error. Received signal 11: Segmentation fault with invalid memory reference.

FishC 发表于 5 天前

您的代码存在几个主要问题导致运行时错误（段错误）：

1. 没有使用数组存储图结构，导致无法处理输入数据
2. 变量使用混乱（如 link 和 ans 被反复覆盖）
3. 使用 goto 导致逻辑混乱
4. 未初始化关键数据结构

以下是修正后的代码（使用拓扑排序）：

#include <stdio.h>
#include <string.h>
#define MAXN 100010

int head, ver, next, tot;
int deg, queue, vis;

void add(int u, int v) {
    ver[++tot] = v;
    next = head;
    head = tot;
    deg++;
}

int main() {
    int N;
    scanf("%d", &N);
   
    memset(head, 0, sizeof(head));
    memset(deg, 0, sizeof(deg));
    tot = 0;
   
    // 读入边并建图
    for (int i = 0; i < N; i++) {
      int a, b;
      scanf("%d %d", &a, &b);
      add(a, b);
      add(b, a);
    }
   
    // 将度为1的节点入队
    int front = 0, rear = 0;
    for (int i = 1; i <= N; i++) {
      if (deg == 1) {
            queue = i;
      }
    }
   
    // 拓扑排序
    while (front < rear) {
      int u = queue;
      vis = 1;// 标记为非环节点
      
      for (int i = head; i; i = next) {
            int v = ver;
            if (--deg == 1) {
                queue = v;
            }
      }
    }
   
    // 输出环上的节点（度>=2的节点）
    for (int i = 1; i <= N; i++) {
      if (!vis) {
            printf("%d ", i);
      }
    }
    return 0;
}

关键修改：
1. 使用邻接表存储图结构（head/ver/next 数组）
2. 添加度数组 deg 记录每个节点的度数
3. 拓扑排序过程：
   - 将所有度为1的节点入队（树节点）
   - 依次移除度为1的节点并更新邻居度数
   - 剩余度≥2的节点即为环上节点
4. 使用 vis 数组标记已处理节点

时间复杂度：O(N)，适用于题目最大数据范围（10^5个点）

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

风眠 发表于 5 天前

FishC 发表于 2025-7-19 19:51
您的代码存在几个主要问题导致运行时错误（段错误）：

1. 没有使用数组存储图结构，导致无法处理输入数 ...

我初始化了
for(int i = 0;i < N+1;i++)
        {
                for(int j = 0;j < N+1;j++)
                {
                        link = 0;
                }
                ans = 0;
        }
错误是这个：
Runtime Error. Received signal 11: Segmentation fault with invalid memory reference.

FishC 发表于 5 天前

风眠 发表于 2025-07-19 19:54
FishC 发表于 2025-7-19 19:51
您的代码存在几个主要 ...

您的代码出现段错误（Segmentation fault）的主要原因是没有正确初始化和使用数据结构。以下是关键问题分析和修正方案：

### 问题分析
1. **变量未正确初始化**：
   - 您使用双重循环试图初始化变量，但 `link` 和 `ans` 只是普通 `int` 变量，不是数组
   - 循环中的赋值 `link = 0;` 和 `ans = 0;` 会被后续覆盖，实际无效

2. **缺少图数据结构**：
   - 题目需要处理树加一条边的图结构
   - 必须使用邻接表或邻接矩阵存储节点连接关系

3. **无效的环检测逻辑**：
   - 使用 `goto` 和手动维护 `link`/`ans` 无法正确检测环
   - 拓扑排序是更可靠的解决方案

### 修正代码
#include <stdio.h>
#include <string.h>
#define MAXN 100010

int head, ver, nxt;
int deg, q, vis;
int tot = 0;

void add(int u, int v) {
    ver[++tot] = v;
    nxt = head;
    head = tot;
    deg++;
}

int main() {
    int N;
    scanf("%d", &N);
   
    memset(head, 0, sizeof(head));
    memset(deg, 0, sizeof(deg));
    tot = 0;
   
    for (int i = 0; i < N; i++) {
      int a, b;
      scanf("%d %d", &a, &b);
      add(a, b);
      add(b, a);
    }
   
    int front = 0, rear = 0;
    for (int i = 1; i <= N; i++) {
      if (deg == 1) {
            q = i;
      }
    }
   
    while (front < rear) {
      int u = q;
      vis = 1;
      for (int i = head; i; i = nxt) {
            int v = ver;
            if (--deg == 1) {
                q = v;
            }
      }
    }
   
    for (int i = 1; i <= N; i++) {
      if (!vis) {
            printf("%d ", i);
      }
    }
    return 0;
}

### 关键改进
1. **使用邻接表存储图**：
   - head 存储每个节点的第一条边
   - ver[] 存储边指向的节点
   - nxt[] 存储下一条边

2. **拓扑排序检测环**：
   - 初始化所有度为1的节点入队
   - 逐步删除度为1的节点（相当于剪枝）
   - 最终未被访问的节点即在环上

3. **正确的初始化**：
   - 使用 memset 初始化数组
   - 显式设置 tot = 0

> 此解法时间复杂度 O(N)，通过拓扑排序高效检测环。注意节点编号从1开始，输出时按升序排列环上节点。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

sfqxx 发表于 5 天前

你应该把题目复制过来给 AI 看（复制 MarkDown）。

不二如是 发表于 4 天前

可以多发~~

风眠 发表于 4 天前

不二如是 发表于 2025-7-20 11:49
可以多发~~

?

查看完整版本: C:Runtime Error.