CSP-J 2019初赛 阅读程序第2题

题面：

// 程序选取很多个<x1, y1> <x2, y2> ... <xm, ym>的数对
// 程序认为 如果两个数对，x或y相等，就认为数对冲突，覆盖之前的选取
// 程序统计，给出的m个数对，解决冲突之后，有多少个数，是没有被选取的
// 即，a[1...n], b[1...n]有多少没有选取

#include<cstdio>

using namespace std;

int n, m;
int a[100], b[100];

// 调试语句
void print(){
    for (int i = 1; i <= n; i++) printf("%d ", i);
    puts("");
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    puts("");
    for (int i = 1; i <= n; i++) printf("%d ", b[i]);
    puts("");
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) a[i] = b[i] = 0;

    // a[x]记录已选中的数对中，与x匹配的y值
    // b[y]记录已选中的数对中，与y匹配的x值
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);

        // 与x匹配的y`，小于y 并且 与y匹配的x`，小于x
        if (a[x] < y && b[y] < x) {
            // 如果当前(x,y)，与已经选用的数对冲突，清空一下标记
            if (a[x] > 0) b[a[x]] = 0;// 原来匹配的y`(a[x]), y`匹配哪个x`，把这个关系清空
            if (b[y] > 0) a[b[y]] = 0;// 原来匹配的x`(b[y]), x`匹配哪个y`，把这个关系清空

            // 更新一下新的匹配关系，x匹配y，y匹配x
            a[x] = y;   
            b[y] = x;
        }

        print();
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 0) ++ans;        // ans统计有多少个x y，没有被选中
        if (b[i] == 0) ++ans;
    }

    printf("%d\n", ans);

    return 0;
}

// 下面给出测试结果
// 观察输入输出，进一步理解程序

数对不冲突

数对中的y冲突