Submission #19289118

---

Source Code Expand

#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;

const int max_n = 200050, max_m = 400050;
int l[2][max_n], mat[max_m];

inline int cm(int x) { return l[1][mat[x]] == x; }

inline int my_min(int a, int b) { return (a < b)? a:b; }
inline int my_max(int a, int b) { return (a > b)? a:b; }

#define gc getchar
inline int read()
{
	int c = gc(), t = 1, n = 0;
	while (isspace(c)) { c = gc(); }
	if (c == '-') { t = -1, c = gc(); }
	while (isdigit(c)) { n = n * 10 + c - '0', c = gc(); }
	return n * t;
}
#undef gc

bool try_match(int i, int t)
{
//	fprintf(stderr, "Trying match %d to %d.\n", i, t);
	bool ret = true, rov = false;

	if (mat[l[cm(t)^1][i]] == i)
		mat[l[cm(t)^1][i]] = -1, rov = true;
	
	if (mat[t] == -1)
		mat[t] = i;
	else if (mat[l[0][mat[t]]] != -1 && mat[l[1][mat[t]]] != -1)
		ret = false;
	else
	{
		if (try_match(mat[t], l[cm(t)^1][mat[t]]))
			mat[t] = i;
		else
			ret = false;
	}
	
	if (!ret && rov)
		mat[l[cm(t)^1][i]] = i;

	return ret;
}

int main()
{
//	freopen("B3.in", "r", stdin);

	memset(mat, -1, sizeof(mat));

	int n = read(), ans = 0, ta, tb;

	for (int i = 0; i < n; i++)
	{
		ta = read(), tb = read();
		l[0][i] = my_min(ta, tb) - 1, l[1][i] = my_max(ta, tb) - 1;
	}
	
	for (int i = 0; i < n; i++)
	{
		if (try_match(i, l[0][i]))
			ans++;
		else if (try_match(i, l[1][i]))
			ans++;
	}

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

	return 0;
}

/*
4
1 2
2 3
3 1
1 4
*/

Submission Info

Judge Result