1003.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

//disjoint set
// [a , b] = s[b] - s[a-1]
//需要离散化 or hash

#include <iostream>
#include <string>
using namespace std;

const int maxL = 65521;
const int Prime = 65521;
int fa[Prime + 100];
int hashData[Prime + 100];
int dis[Prime + 100];// dis 可以为0或者1,0代表跟他的parent奇偶性相同，1代表相反
int ans;
void init()
{
	int i;
	for(i = 0; i <= Prime; i++ )
		fa[i] = i, dis[i] = 0;
	memset( hashData, 255, sizeof(hashData) );
}

int hash( int x )
{
	int t;
	t = x%Prime;
	while( hashData[t] >= 0 && (hashData[t] != x ) )
	{ t = (t+1)%Prime; }
	hashData[t] = x;
	return t;			//这处写成 return hashData[t] = x;害我错了N次。。。55555
}
int findSet( int x )
{	
	if( fa[x] != x )
	{
		int t = fa[x];
		fa[x] = findSet( fa[x] );
		dis[x] = (dis[x] + dis[t])%2;
	}	
	return fa[x];
}
int main()
{
//	freopen("1003.in","r",stdin);
	int i, q;
	int a, b;
	string EvenOrOdd;
	int dab;
	int l;
	while ( cin >> l, l != -1 )
	{
		init();
		cin >> q;
		ans = q;
		for( i = 1; i <= q; i++ )
		{
			cin >> a >> b,a--;// s[i]为 1~i区间的1的奇偶性
			cin >> EvenOrOdd;
			a = hash(a),b = hash(b);
			if( EvenOrOdd == "even" ) dab = 0;
			if( EvenOrOdd == "odd" ) dab = 1;
			if( findSet(a) != findSet(b) )
			{
				
				dis[ fa[b] ] = ( dis[a]-dis[b]-dab +2 ) %2 , // dis[a]==dab+dis[b]+dis[ fa[b] ]
				fa[ fa[ b ] ] = fa[a];
				
			}
			else if( dis[a] != (dis[b]+dab)%2 )
			{
				ans = i - 1;
				break;
			}
		}
		for( ; i< q; i++ )
		{
			cin >> a >> b >> EvenOrOdd;
		}
		cout << ans << endl;
	}
	return 0;
}