3286169_ac_47ms_4116k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int r, c;
int map[1001][1001];
int link[1001], b[1001];

int find(int v)
{
	int i;

	for(i = 1; i <= map[v][0]; i++)
	{
		if(!b[map[v][i]])
		{
			b[map[v][i]] = 1;
			if(!link[map[v][i]]||find(link[map[v][i]]))
			{
				link[map[v][i]] = v;
				return 1;
			}
		}
	}
	return 0;
}

int tmp[1001];

int main()
{
	int x, i;
	int fail;
	int a, v;

	scanf("%d",&x);
	while(x-- > 0)
	{
		scanf("%d%d",&r,&c);
		memset(link,0,sizeof(link));
		memset(map,0,sizeof(map));
		for(i = 1; i <= c; i++)
		{
			scanf("%d%d",&a,&v);
			map[a][++map[a][0]] = i;
			map[v][++map[v][0]] = i;
			tmp[i] = a;
		}
		fail = 0;
		for(i = 1; i <= r; i++)
		{
			memset(b,0,sizeof(b));
			if(!find(i))
			{
				fail = 1;
				break;
			}
		}
		if(fail)
		{
			puts("NO");
			continue;
		}
		for(i = 1; i <= c; i++)
		{
			if(link[i]==0)
			{
				link[i] = tmp[i];
			}
			printf("%d ",link[i]);
		}
		putchar('\n');
	}
	return 0;
}