uva 10763 - Foreign Exchange

我的想法是都存到一个数组里，录入的时候将如果后面一个数字小，就交换下位置，然后按照两个数字依次排序，排序之后正常情况应该是依次两个两个相等，否则就有问题。

有人是from和to分别放到两个数组，依次排序后一对一比较，但是这种情况有bug，比如A到B，B到C，C到A理论上应该No，这种解法确是YES（虽然据说好像没有这种case，也能AC...）。

 

#include<stdio.h>
#include<stdlib.h>

#define MAX 2*500000+5
typedef struct Exchange {
	int from;
	int to;
} Exchange;

Exchange ex[MAX];

int cmp(const void*a, const void*b) {
	Exchange *aa = (Exchange*) a;
	Exchange *bb = (Exchange*) b;
	if (aa->from != bb->from)
		return aa->from - bb->from;
	else
		return aa->to - bb->to;

}

int main() {
	int n;
	int a, b;
	while (scanf("%d", &n)) {
		if (n == 0)
			break;
		int i;
		for (i = 0; i < n; i++) {
			scanf("%d%d", &a, &b);
			if (a < b) {
				ex[i].from = a;
				ex[i].to = b;
			} else {
				ex[i].from = b;
				ex[i].to = a;
			}
		}

		qsort(ex, n, sizeof(Exchange), cmp);

		int ok = 1;
		for (i = 0; i < n; i += 2) {
			if (ex[i].from != ex[i + 1].from || ex[i].to != ex[i + 1].to) {
				ok = 0;
				break;
			}
		}

		if (ok)
			printf("YES\n");
		else
			printf("NO\n");

	}

	return 0;
}