2838.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:2838  User Id:fzk 
Memory:7960K  Time:1732MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>

struct edge {
	edge *pri;
	edge *next;
};

edge *e[1010];
edge temp[1010][1010];

void add( int from, int to ) {
	temp[from][to].next = e[from];
	temp[from][to].pri = 0;
	if( e[from] ) e[from]->pri = temp[from]+to;
	e[from] = temp[from]+to;
}

void del( int from, int to ) {
	if( temp[from][to].pri )
		temp[from][to].pri->next = temp[from][to].next;
	if( temp[from][to].next )
		temp[from][to].next->pri = temp[from][to].pri;
	if( e[from] == temp[from]+to )
		e[from] = e[from]->next;
}

bool search( int from, int to ) {
	bool sign[1010] = { false };
	int qh = 0, qe = 0, q[1010], t, k;
	
	q[qh++] = from;
	sign[from] = true;

	while( qe < qh ) {
		t = q[qe++];
		for( edge *p = e[t]; p; p = p->next )
			if( !sign[k=p-temp[t]] ) {
				if( k == to )
					return true;
				sign[k] = true;
				q[qh++] = k;
			}
	}

	return false;
}

int main( ) {
	int u, v, n, q;
	char c[2];
	scanf( "%d%d", &n, &q );
	while( q-- ) {
		scanf( "%1s%d%d", c, &u, &v );
		if( c[0] == 'I' ) {
			add( u, v );
			add( v, u );
		}
		else if( c[0] == 'D' ) {
			del( u, v );
			del( v, u );
		}
		else
			printf( "%c\n", (u==v||search( u, v ))?'Y':'N' );

	}
	return 0;
}