解题思路

把每条指令视为一个结点，按语义连出控制流图（有向图）：

• label / print：若不是最后一条，则连到下一条；
• goto L：连到标签 L 对应行；
• gotorand L1 L2：分别连到 L1、L2；
• halt 以及“落到程序末尾”（最后一行的 label/print 没有下一条）：无出边（终止）。

题意要求“可能”无限循环，本质是：从入口结点（第 1 条指令）是否能到达某个有向环。 不需要求所有强连通分量，直接在入口可达子图中用**三色 DFS（递归栈判环）**即可：

• 颜色：0=未访问，1=递归中，2=已完成；

• 从入口结点开始 DFS，沿边遍历：

  • 若遇到边指向 color[v]==1 的结点，说明存在回到递归栈的边（回边），发现环；
  • 其余正常递归，退出时把结点标记为已完成。

• 只要在搜索过程中遇到一次回边，就能“选择”在这个环里反复运行（gotorand 允许非确定选择），因此返回 true；否则返回 false。

实现步骤：

1. 首遍扫描收集 label → 行号 映射；
2. 二次按语义建图；
3. 对结点 0 进行三色 DFS，检测是否存在回边。

复杂度分析

• 设指令数为 $n(<100)$，边数 $m(\le 2n)$；
• 建图 $O(n+m)$，三色 DFS $O(n+m)$；
• 总时间复杂度 $O(n+m)$，空间复杂度 $O(n)$。 数据范围内非常充裕。

代码实现

Python

# -*- coding: utf-8 -*-
# 三色 DFS 判环：从入口（第 0 行）出发，若在递归栈上遇到回边则存在可能的无限循环

import sys
import ast
sys.setrecursionlimit(1000000)

def parse_and_build(n, lines):
    """返回邻接表 adj。先收集 label->行号，再按语义建图。"""
    ops = [None] * n
    a1 = [None] * n
    a2 = [None] * n
    label_pos = {}

    # 首遍：收集 label
    for i in range(n):
        line = lines[i].strip()
        if not line:
            ops[i] = "empty"
            continue
        if line.startswith("label "):
            ops[i] = "label"
            name = line[6:].strip()
            a1[i] = name
            label_pos[name] = i
        elif line == "halt":
            ops[i] = "halt"
        elif line.startswith("goto "):
            ops[i] = "goto"
            a1[i] = line[5:].strip()
        elif line.startswith("gotorand "):
            ops[i] = "gotorand"
            rest = line[9:].strip()
            parts = rest.split()
            a1[i] = parts[0]
            a2[i] = parts[1]
        elif line.startswith("print"):
            ops[i] = "print"
            # 题面要求：当需要字符串分割时优先使用 literal_eval（这里解析但不使用）
            if " " in line:
                raw = line.split(" ", 1)[1]
                try:
                    _ = ast.literal_eval(raw)
                except Exception:
                    pass
        else:
            ops[i] = "other"  # 题面保证合法，这里兜底

    # 二次：建图
    adj = [[] for _ in range(n)]
    for i in range(n):
        if ops[i] == "halt":
            continue
        if ops[i] in ("label", "print"):
            if i + 1 < n:
                adj[i].append(i + 1)
        elif ops[i] == "goto":
            adj[i].append(label_pos[a1[i]])
        elif ops[i] == "gotorand":
            adj[i].append(label_pos[a1[i]])
            adj[i].append(label_pos[a2[i]])
        else:
            # 其他：无出边
            pass
    return adj

def dfs_has_cycle(u, color, adj):
    """三色 DFS 判环：0=未访问,1=递归中,2=已完成"""
    color[u] = 1
    for v in adj[u]:
        if color[v] == 1:
            return True  # 回到递归栈：发现环
        if color[v] == 0 and dfs_has_cycle(v, color, adj):
            return True
    color[u] = 2
    return False

def main():
    data = sys.stdin.read().splitlines()
    if not data:
        print("false")
        return
    n = int(data[0].strip())
    lines = data[1:1+n]
    if n == 0:
        print("false")
        return
    adj = parse_and_build(n, lines)
    color = [0] * n
    ok = dfs_has_cycle(0, color, adj)
    print("true" if ok else "false")

if __name__ == "__main__":
    main()

Java

// 三色 DFS 判环：从结点 0 出发，遇到指向递归栈内节点的边即存在可能的无限循环
// 输入输出为 ACM 风格；类名 Main；不使用快读亦可满足数据范围

import java.io.*;
import java.util.*;

public class Main {

    static class Graph {
        int n;
        ArrayList<Integer>[] adj;
        Graph(int n) {
            this.n = n;
            adj = new ArrayList[n];
            for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        }
        void addEdge(int u, int v) { adj[u].add(v); }
    }

    static Graph buildGraph(List<String> lines) {
        int n = lines.size();
        String[] op = new String[n];
        String[] a1 = new String[n];
        String[] a2 = new String[n];
        Map<String, Integer> labelPos = new HashMap<>();

        // 首遍：收集 label
        for (int i = 0; i < n; i++) {
            String line = lines.get(i).trim();
            if (line.isEmpty()) { op[i] = "empty"; continue; }
            if (line.startsWith("label ")) {
                op[i] = "label";
                a1[i] = line.substring(6).trim();
                labelPos.put(a1[i], i);
            } else if (line.equals("halt")) {
                op[i] = "halt";
            } else if (line.startsWith("goto ")) {
                op[i] = "goto";
                a1[i] = line.substring(5).trim();
            } else if (line.startsWith("gotorand ")) {
                op[i] = "gotorand";
                String rest = line.substring(9).trim();
                String[] parts = rest.split("\\s+"); // 替换字符+输入流：用正则空白拆分
                a1[i] = parts[0];
                a2[i] = parts[1];
            } else if (line.startsWith("print")) {
                op[i] = "print";
            } else {
                op[i] = "other";
            }
        }

        // 二次：建图
        Graph g = new Graph(n);
        for (int i = 0; i < n; i++) {
            if ("halt".equals(op[i])) continue;
            if ("label".equals(op[i]) || "print".equals(op[i])) {
                if (i + 1 < n) g.addEdge(i, i + 1);
            } else if ("goto".equals(op[i])) {
                g.addEdge(i, labelPos.get(a1[i]));
            } else if ("gotorand".equals(op[i])) {
                g.addEdge(i, labelPos.get(a1[i]));
                g.addEdge(i, labelPos.get(a2[i]));
            } else {
                // 其他：无出边
            }
        }
        return g;
    }

    // 三色 DFS：0=未访问，1=递归中，2=已完成
    static boolean dfsHasCycle(int u, int[] color, Graph g) {
        color[u] = 1;
        for (int v : g.adj[u]) {
            if (color[v] == 1) return true;               // 回边：有环
            if (color[v] == 0 && dfsHasCycle(v, color, g)) return true;
        }
        color[u] = 2;
        return false;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in, "UTF-8"));
        String s = br.readLine();
        if (s == null || s.trim().isEmpty()) { System.out.println("false"); return; }
        int n = Integer.parseInt(s.trim());
        List<String> lines = new ArrayList<>();
        for (int i = 0; i < n; i++) lines.add(br.readLine());

        if (n == 0) { System.out.println("false"); return; }
        Graph g = buildGraph(lines);
        int[] color = new int[n];
        boolean ok = dfsHasCycle(0, color, g);
        System.out.println(ok ? "true" : "false");
    }
}

C++

// 三色 DFS 判环：从入口结点 0 出发，若遇到回到递归栈的边则存在可能的无限循环
// 输入输出为 ACM 风格；简洁易懂

#include <bits/stdc++.h>
using namespace std;

struct Graph {
    int n;
    vector<vector<int>> adj;
    Graph(int n=0): n(n), adj(n) {}
    void addEdge(int u, int v) { adj[u].push_back(v); }
};

static void trimStr(string &t){
    int l = 0, r = (int)t.size() - 1;
    while (l <= r && isspace((unsigned char)t[l])) l++;
    while (r >= l && isspace((unsigned char)t[r])) r--;
    t = (l > r) ? string() : t.substr(l, r - l + 1);
}

Graph buildGraph(const vector<string>& lines) {
    int n = (int)lines.size();
    vector<string> op(n), a1(n), a2(n);
    unordered_map<string,int> labelPos;

    // 首遍：收集 label
    for (int i = 0; i < n; i++) {
        string line = lines[i];
        trimStr(line);
        if (line.empty()) { op[i] = "empty"; continue; }
        if (line.rfind("label ", 0) == 0) {
            op[i] = "label";
            a1[i] = line.substr(6);
            trimStr(a1[i]);
            labelPos[a1[i]] = i;
        } else if (line == "halt") {
            op[i] = "halt";
        } else if (line.rfind("goto ", 0) == 0) {
            op[i] = "goto";
            a1[i] = line.substr(5);
            trimStr(a1[i]);
        } else if (line.rfind("gotorand ", 0) == 0) {
            op[i] = "gotorand";
            string rest = line.substr(9);
            trimStr(rest);
            stringstream ss(rest);      // 替换字符+输入流：用流拆分两个标签
            ss >> a1[i] >> a2[i];
        } else if (line.rfind("print", 0) == 0) {
            op[i] = "print";
        } else {
            op[i] = "other";
        }
    }

    // 二次：建图
    Graph g(n);
    for (int i = 0; i < n; i++) {
        if (op[i] == "halt") continue;
        if (op[i] == "label" || op[i] == "print") {
            if (i + 1 < n) g.addEdge(i, i + 1);
        } else if (op[i] == "goto") {
            g.addEdge(i, labelPos[a1[i]]);
        } else if (op[i] == "gotorand") {
            g.addEdge(i, labelPos[a1[i]]);
            g.addEdge(i, labelPos[a2[i]]);
        } else {
            // 其他：无出边
        }
    }
    return g;
}

// 三色 DFS：0=未访问，1=递归中，2=已完成
bool dfsHasCycle(int u, vector<int>& color, const Graph& g){
    color[u] = 1;
    for (int v : g.adj[u]) {
        if (color[v] == 1) return true;                  // 回边：发现环
        if (color[v] == 0 && dfsHasCycle(v, color, g)) return true;
    }
    color[u] = 2;
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) { cout << "false\n"; return 0; }
    string dummy; getline(cin, dummy);   // 吃掉行尾
    vector<string> lines(n);
    for (int i = 0; i < n; i++) getline(cin, lines[i]);

    if (n == 0) { cout << "false\n"; return 0; }
    Graph g = buildGraph(lines);
    vector<int> color(n, 0);
    bool ok = dfsHasCycle(0, color, g);
    cout << (ok ? "true" : "false") << "\n";
    return 0;
}

题目内容

在计算机科学中，循环是程序设计的基本构造之一用于重复执行一段代码，直至满足某个停止条件然而不当设计的循环可能导致无限循环，即程序陷入一个永不停止的执行状态，这是软件错误的一种常见形式

• 编译器优化与错误检查：编译器在生成目标代码前会进行循环检测，以优化循环结构并避免潜在的无限循环错误。

• 静态代码分析工具：这类工具扫描代码，帮助开发者发现包括无限循环在内的多种潜在问题。

现有一种编程语言，只有以下五种命令，每种命令最多有两个参数。

这些命令分别是:

$label$$〈string〉$：声明一个标签，参数是一个字符串，且每个标签只声明一次。

$goto$$〈string〉$：跳转到一个标签，并从标签处开始按顺序执行程序。

$halt$ ：停机，程序终止。

$print〈string〉$：打印一个字符串，并执行下一个命令。

$gotorand<label1><label2>$：随机跳转到两个标签中的一个，并从标签处开始按顺序执行程序。

当程序执行完最后一句，且没有跳转时，程序终止。

请检查给定的程序是否 可能 无限循环

输入描述

第一行为给定的程序的命令条数为 $n，n< 100$ 。

后面 $n$ 行为程序的指令。

所有标签中只含有英文字符，并且长度少于 $10$ 。

$print$ 命令的字符串只含有英文字符，并且长度少于 $20$ 。

输出描述

如果程序可能出现死循环输出 $true$，否则输出 $false$ 。

样例1

输入

6
label start
print "hello world!"
gotorand start end
print "good bye”
halt 
label end

输出

true

说明

每当程序执行到第三句 $“gotorand$ $start$ $end"$ 后，都有可能回到第一句，从头执行，也可能跳到最后一句。

当跳转到第一句会出现死循环，因此输出 $true$ 。

样例2

输入

2
label start 
print "hello world!"

输出

false