4083477_wa.cc

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

#include <stdio.h>
//#pragma comment(linker, "/STACK:16777216")

int p[6000010];
int rank[6000010];
int n;

int findset(int x)
{
	if (x != p[x])
		return p[x] = findset(p[x]);
	else
		return p[x];
}

void link(int x, int y)
{
	if (rank[x] > rank[y])
	{
		p[y] = x;
	}
	else
	{
		p[x] = y;
		if (rank[x] == rank[y])
		{
			rank[y]++;
		}
	}
}

void report(bool value)
{
	if (!value)
	{
		puts("error occured");
	}
}

int main()
{
	char command, m_char;
	int src, dst, nnn;
	int srcstep, dststep;

	//puts("OK?");

	//freopen("f.in", "r", stdin);
	//freopen("res.txt", "w", stdout);
	while ((command = getchar()) != EOF)
	{
		//printf("%c\n", command);
		getchar();
		if (command == 'd' || command == 'D')
		{
			scanf("%d", &n);
			//printf("n is %d\n", n);
			getchar(), getchar();
			for (int i = 1; i <= n; i++)
			{
				p[i] = i, rank[i] = 0;
			}
			continue;
		}
		scanf("%d%d", &src, &dst);
		//report(src > 0 && src <= n && dst > 0 && dst <= n);
		m_char = getchar();
		if (m_char == ' ')
		{
			scanf("%d", &nnn);
			m_char = getchar();
			if (m_char == ' ')
			{
				scanf("%d", &dststep);
				m_char = getchar();
				if (m_char == ' ')
				{
					scanf("%d", &srcstep);
					getchar(), getchar();
				}
				else
				{
					getchar();
					srcstep = 0;
				}
			}
			else
			{
				getchar();
				srcstep = 0, dststep = 1;
			}
		}
		else
		{
			getchar();
			nnn = 1, srcstep = 0, dststep = 0;
		}
		if (command == 'C' || command == 'c')
		{
			if (srcstep == 0 && dststep == 0)
			{
				if (!(src < 1 || src > n || dst < 1 || dst > n))
				{
					link(findset(src), findset(dst));
				}
				continue;
			}
			for (int i = 0; i < nnn; i++, src += srcstep, dst += dststep)
			{
				if (src < 1 || src > n || dst < 1 || dst > n)
				{
					continue;
				}
				link(findset(src), findset(dst));
			}
			continue;
		}

		int ans = 0;

		if (srcstep == 0 && dststep == 0)
		{
			if (!(src < 1 || src > n || dst < 1 || dst > n) && findset(src) == findset(dst))
			{
				ans = nnn;
			}
		}
		else
		{
			for (int i = 0; i < nnn; i++, src += srcstep, dst += dststep)
			{
				if (src < 1 || src > n || dst < 1 || dst > n)
				{
					continue;
				}
				ans += (findset(src) == findset(dst));
			}
		}
		printf("%d - %d\n", ans, nnn - ans);
	}
	return 0;
}