pku2838.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define size 1001

typedef struct Node
{
	int id, next;
} Node;

Node G[size * 19];
int G_end;
int N, Q;

void Insert(int a, int b)
{
	int p = a;
	while (G[p].next)
	{
		p = G[p].next;
	}
	G[p].next = G_end;
	G[G_end++].id = b;
}

void Delete(int a, int b)
{
	int p = a;
	int q;
	while (p)
	{
		q = p;
		p = G[p].next;
		if (G[p].id == b)
		{
			G[q].next = G[p].next;
			return;
		}
	}
}

int BFS(int a, int b)
{
	int Qu[1100];
	int v[1100];
	int p;
	int head, end;
	Qu[0] = a;
	head = 0;
	end = 1;
	memset(v, 0, sizeof(v));
	v[a] = 1;
	while (head < end)
	{
		p = Qu[head];
		while (G[p].next)
		{
			p = G[p].next;
			if (v[G[p].id] == 0)
			{
				if (G[p].id == b)
					return 1;
				v[G[p].id] = 1;
				Qu[end++] = G[p].id;
			}
		}
		head++;
	}
	return 0;
}

int main()
{
	int a, b, t;
	char s[3];
	while (EOF != scanf("%d %d", &N, &Q))
	{
		memset(G, 0, sizeof(G));
		G_end = N + 10;
		while (Q--)
		{
			scanf("%s %d %d", s, &a, &b);
			if (s[0] == 'I' && a != b)
			{
				Insert(a, b);
				Insert(b, a);
			}
			else if (s[0] == 'D')
			{
				Delete(a, b);
				Delete(b, a);
			}
			else
			{
				printf("%s\n", (a == b) || BFS(a, b) ? "Y" : "N");
			}
		}
	}
}