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

typedef struct
{
	int hash1;
	int hash2;
}Hash;

Hash hash[10000];
int tab[10000];
int x, y;

//当前冲突的单元 and 要放进的值
int solve ( int slot, int value )
{
	int temp;

	temp = tab[slot];
    tab[slot] = value;

	//被替换区域任何一个可以使用则将被替换的放入
	if ( tab[hash[temp-1].hash1] == 0 )
	{
		tab[hash[temp-1].hash1] = temp;
		return 1;
	}
	if ( tab[hash[temp-1].hash2] == 0 )
	{
		tab[hash[temp-1].hash2] = temp;
		return 1;
	}

	//选择和slot不一样的单元递归下一个处理
	if ( slot == hash[temp-1].hash1 )
	{
        //和初始的情况相同则返回0，发现循环
		if ( hash[temp-1].hash2 == x && temp == y )
			return 0;
		//否则递归下一个处理过程
		else
	    	return solve ( hash[temp-1].hash2, temp );
	}
	else 
	{
		if ( hash[temp-1].hash1 == x && temp == y )
			return 0;
		else
			return solve ( hash[temp-1].hash1, temp );
	}
}

int main ()
{
	int t, i, j, m, n;

	scanf ( "%d", &t );

	for ( i = 0; i < t; i ++ )
	{
		scanf ( "%d%d", &m, &n );

		for ( j = 0; j < m; j ++ )
			scanf ( "%d%d", &hash[j].hash1, &hash[j].hash2) ;

		memset ( tab, 0, sizeof ( int ) * m );

		for ( j = 0; j < m; j++ )
		{
			//如果没有可放入，则直接放入并处理下一个
			if ( tab[hash[j].hash1] == 0 )
			{
				tab[hash[j].hash1] = j + 1;

				if ( j == m - 1 )
					puts ( "successful hashing" );
				continue;
			}
			if ( tab[hash[j].hash2] == 0 )
			{
				tab[hash[j].hash2] = j + 1;

				if ( j == m - 1 )
					puts ( "successful hashing" );
				continue;
			}		

			x= hash[j].hash1;
			y = j + 1;

			if ( solve ( hash[j].hash1, j + 1 ) )
			{
				if ( j == m - 1 )
			    	puts ( "successful hashing" );
			}
			else
			{
				puts ( "rehash necessary" );
				break;
			}
		}
	}

	return 0;
}

• 判断是否死循环好像不是这样搞的 (29) zfy0701 2008-07-16 00:52:03