ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 G: 小凯用git

内存限制：512 MB 时间限制：10 S
题面：传统 评测方式：文本比较 上传者：
提交：10 通过：1
返回比赛提交提交记录

题目描述



git是一个分布式版本控制系统。

本题目要求你实现一个简单的git分支管理模拟，你需要从输入中获取指令，并且在本地执行。

你需要实现的指令如下：

接下来将依次介绍各个指令和基本概念

  1. 提交节点（Commit Node）：

    • 每个提交节点有一个唯一的整数编号。
    • 初始时有一个编号为1的节点。
    • 新节点的编号是当前存在的节点数量 + 1。
    • 节点可以有父亲（parent）：
      • 普通提交有一个父亲（前一个节点）。
      • 合并提交有两个父亲（当前分支的节点和被合并分支的节点）。

  2. 分支（Branch）：

    • 分支是一个指向某个提交节点的指针。
    • 分支有唯一的名字（字符串）。
    • 初始时有一个名为main的分支，指向节点1。

  3. HEAD：

    • HEAD是一个指向当前分支的指针。
    • 初始时HEAD指向main分支。

  4. 指令：

    • commit：
      • 创建一个新节点，编号为当前节点数量 + 1。
      • 新节点的父亲是当前分支指向的节点。
      • 将当前分支移动到新节点。
    • branch (branch_name) [node]：
      • 在指定的node（如果没有指定，则为当前分支指向的节点）创建一个名为branch_name的新分支。
      • 如果branch_name已存在，则跳过。
    • branch -d (branch_name)：
      • 删除名为branch_name的分支。
      • 如果分支不存在，则跳过。
    • merge (branch_name)：
      • 如果 指定分支 branch_name 的所有祖先包括自己组成的集合 不为 当前分支所有祖先包括自己组成的集合的子集并且当前分支的祖先集合包括自己 不为 指定分支 branch_name 所有祖先包括自己的子集，那么创建一个新节点，编号为当前节点数量 + 1。
      • 新节点的两个父亲分别是当前分支指向的节点和branch_name分支指向的节点。
      • 将当前分支移动到新节点。
      • 否则如果当前分支的祖先集合包括自己是指定分支 branch_name 所有祖先包括自己的子集，将当前分支移动到branch_name 所在的节点。
      • 否则不操作
    • checkout (branch_name)：
      • 将HEAD切换到名为branch_name的分支（即当前分支变为branch_name）。
    • reset [node]：
      • 将当前分支移动到指定的node（如果没有指定，则为当前分支指向的节点）。
      • 注意：reset不会创建新节点，只是移动分支指针。

数据保证不会删除当前分支，不会checkout或merge一个没有出现的分支，保证node一定是已出现过的节点编号。

开始时，当前分支为main，指向一个提交节点，编号为1。




输入格式

多组数据，第一行一个整数 1≤T≤40 表示有 TT 组数据。

每组数据第一行一个整数 nn 满足1≤n≤5000，表示有 nn 条语句需要处理。

保证 ∑n≤105 , branch_name的长度 1≤len≤20，branch_name只包含大小写字母和数字

输出格式

对于每组数据，先输出分支数量 N，然后 按字典序升序排列后 输出 NN行分支名 S 和分支所在节点 M 。然后输出总节点数 W ，接下来 W 行 每行先输出节点的父亲数量 P，按节点编号升序排列后 输出 P个整数，代表父亲的节点编号。

输入样例 复制 

1
12
commit
branch bugfix
commit
checkout bugfix
commit
merge main
merge main
checkout main
merge bugfix
commit
reset 2
commit

输出样例 复制 

2
bugfix 5
main 7
7
0 
1 1 
1 2 
1 2 
2 3 4 
1 5 
1 2

数据范围与提示

初始状态如下：

  • 提交节点：只有一个节点 1（初始节点）。
  • 分支：main 指向节点 1。
  • HEAD：指向 main。

指令执行过程：

  1. commit:
    • 创建一个新节点，编号为 2（当前节点数量 1 + 1）。
    • 新节点 2 的父亲是当前分支 main 指向的节点 1。
    • 将 main 分支移动到节点 2。
    • 状态：
      • 节点：1（父：无），2（父：1）。
      • 分支：main -> 2，HEAD -> main。
  2. branch bugfix:
    • 在当前分支 main 指向的节点 2 创建一个新分支 bugfix。
    • bugfix 指向节点 2。
    • 状态：
      • 节点：1, 2。
      • 分支：main -> 2, bugfix -> 2。
      • HEAD -> main。
  3. commit:
    • 创建一个新节点 3（当前节点数量 2 + 1）。
    • 新节点 3 的父亲是 main 指向的节点 2。
    • 将 main 分支移动到节点 3。
    • 状态：
      • 节点：1, 2（父：1），3（父：2）。
      • 分支：main -> 3, bugfix -> 2。
      • HEAD -> main。
  4. checkout bugfix:
    • 将 HEAD 切换到 bugfix 分支。
    • 当前分支现在是 bugfix，指向节点 2。
    • 状态：
      • 节点：1, 2, 3。
      • 分支：main -> 3, bugfix -> 2。
      • HEAD -> bugfix。
  5. commit:
    • 创建一个新节点 4（当前节点数量 3 + 1）。
    • 新节点 4 的父亲是 bugfix 指向的节点 2。
    • 将 bugfix 分支移动到节点 4。
    • 状态：
      • 节点：1, 2（父：1），3（父：2），4（父：2）。
      • 分支：main -> 3, bugfix -> 4。
      • HEAD -> bugfix。
  6. merge main:
    • 当前分支是 bugfix（指向 4），要合并 main（指向 3）。
    • 检查 main 的所有祖先（3, 2, 1）是否是 bugfix 的所有祖先（4, 2, 1）的子集：
      • main 的祖先集合：{3, 2, 1}。
      • bugfix 的祖先集合：{4, 2, 1}。
      • {3, 2, 1} 不是 {4, 2, 1} 的子集（因为 3 不在 {4, 2, 1} 中）。
    • 因此需要创建一个合并节点 5（当前节点数量 4 + 1）。
    • 新节点 5 的两个父亲是 bugfix 指向的 4 和 main 指向的 3。
    • 将 bugfix 分支移动到节点 5。
    • 状态：
      • 节点：1, 2, 3, 4, 5（父：4 和 3）。
      • 分支：main -> 3, bugfix -> 5。
      • HEAD -> bugfix。
  7. merge main:
    • 当前分支是 bugfix（指向 5），要合并 main（指向 3）。
    • 检查 main 的所有祖先（3, 2, 1）是否是 bugfix 的所有祖先（5, 4, 3, 2, 1）的子集：
      • main 的祖先集合：{3, 2, 1}。
      • bugfix 的祖先集合：{5, 4, 3, 2, 1}。
      • {3, 2, 1} 是 {5, 4, 3, 2, 1} 的子集。
    • 进一步检查 bugfix 的祖先是否是 main 的祖先的子集：
      • bugfix 的祖先集合 {5, 4, 3, 2, 1} 不是 {3, 2, 1} 的子集（因为 5 和 4 不在 {3, 2, 1} 中）。
    • 因此不进行任何操作（merge 无效果）。
    • 状态保持不变。
  8. checkout main:
    • 将 HEAD 切换到 main 分支。
    • 当前分支现在是 main，指向节点 3。
    • 状态：
      • 节点：1, 2, 3, 4, 5。
      • 分支：main -> 3, bugfix -> 5。
      • HEAD -> main。
  9. merge bugfix:
    • 当前分支是 main（指向 3），要合并 bugfix（指向 5）。
    • 检查 bugfix 的所有祖先（5, 4, 3, 2, 1）是否是 main 的所有祖先（3, 2, 1）的子集：
      • bugfix 的祖先集合：{5, 4, 3, 2, 1}。
      • main 的祖先集合：{3, 2, 1}。
      • {5, 4, 3, 2, 1} 不是 {3, 2, 1} 的子集（因为 5 和 4 不在 {3, 2, 1} 中）。
    • 进一步检查 main 的祖先是否是 bugfix 的祖先的子集：
      • main 的祖先集合 {3, 2, 1} 是 {5, 4, 3, 2, 1} 的子集。
    • 因此将 main 分支移动到 bugfix 指向的节点 5。
    • 状态：
      • 节点：1, 2, 3, 4, 5。
      • 分支：main -> 5, bugfix -> 5。
      • HEAD -> main。
  10. commit:
    • 创建一个新节点 6（当前节点数量 5 + 1）。
    • 新节点 6 的父亲是 main 指向的节点 5。
    • 将 main 分支移动到节点 6。
    • 状态：
      • 节点：1, 2, 3, 4, 5, 6（父：5）。
      • 分支：main -> 6, bugfix -> 5。
      • HEAD -> main。
  11. reset 2:
    • 将当前分支 main 移动到节点 2。
    • 不创建新节点。
    • 状态：
      • 节点：1, 2, 3, 4, 5, 6。
      • 分支：main -> 2, bugfix -> 5。
      • HEAD -> main。
  12. commit:
    • 创建一个新节点 7（当前节点数量 6 + 1）。
    • 新节点 7 的父亲是 main 指向的节点 2。
    • 将 main 分支移动到节点 7。
    • 状态：
      • 节点：1, 2, 3, 4, 5, 6, 7（父：2）。
      • 分支：main -> 7, bugfix -> 5。
      • HEAD -> main。

最终状态：

  • 提交节点：
    • 1（初始节点，无父节点）。
    • 2（父：1）。
    • 3（父：2）。
    • 4（父：2）。
    • 5（父：4 和 3）。
    • 6（父：5）。
    • 7（父：2）。
  • 分支：
    • main 指向 7。
    • bugfix 指向 5。
  • HEAD 指向 main。

分类标签