pku1719.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 76 行

#include <stdio.h>
#include <string.h>
#include <vector>
#define maxn 1002
using namespace std;

vector <int> p[maxn];
int match[maxn];
int y[maxn][2];
bool v[maxn];
int R, C;
int a, b;

bool DFS(int x)
{
	int i, t;
	for (i = 0; i < p[x].size(); i++)
	{
		if (!v[p[x][i]])
		{
			t = match[p[x][i]];
			v[p[x][i]] = true;
			match[p[x][i]] = x;
			if (t == -1 || DFS(t))
				return true;
			match[p[x][i]] = t;
		}
	}
	return false;
}

void solve()
{
	int i, j;
	scanf("%d %d", &R, &C);
	memset(p, false, sizeof(p));
	for (i = 1; i <= C; i++)
	{
		scanf("%d %d", &a, &b);
		p[a].push_back(i);
		p[b].push_back(i);
		y[i][0] = a;
		y[i][1] = b;
	}
	memset(match, -1, sizeof(match));
	for (i = 1; i <= R; i++)
	{
		memset(v, false, sizeof(v));
		if (!DFS(i))
			break;
	}
	if (i <= R)
	{
		printf("NO\n");
	}
	else
	{
		for (i = 1; i <= C; i++)
		{
			if (match[i] != -1)
				printf("%d ", match[i]);
			else
				printf("%d ", y[i][0]);
		}
		printf("\n");
	}
}

int main()
{
	int x;
	scanf("%d", &x);
	while (x--)
		solve();
}