poj2352，poj 1733 ParityGame 并查集 离散化

这道题poj1733 和 hdu 3038类似，闭区间那里的原理相同。

本题的两段代码的区别只有find()函数不同
但是感觉没有区别的呀

poj2352，AC:

int find(int x)
{if (par[x] == -1)return x;int tmp = find(par[x]);val[x] ^= val[par[x]];return par[x] = tmp;
}

WA:

int find(int x)//错误写法！
{if (par[x] == -1)return x;//不可以改为par[x]val[x] ^= val[par[x]];return par[x] = find(par[x]);
}

AC的代码

#pragma warning(disable:4996)
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<ctype.h>
#include<memory.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
#define ll long long int
using namespace std;
const int maxn = 20000;int n, m;
int par[maxn];
int val[maxn];
map<int, int> Map;
int cnt = 0;//int find(int x)//错误写法！
//{
//	if (par[x] == -1)
//		return x;//不可以改为par[x]
//	val[x] ^= val[par[x]];
//	return par[x] = find(par[x]);
//}
int find(int x)
{if (par[x] == -1)return x;int tmp = find(par[x]);val[x] ^= val[par[x]];//cout << "va[x]=" << val[x] << " par[x]=" << par[x] << " val[par[x]]=" << val[par[x]] << endl;return par[x] = tmp;
}void ini()
{//for (int i = 0; i < n; i++)//{//	//par[i] = i;////	par[i] = -1;//	val[i] = 0;//}memset(par, -1, sizeof(par));memset(val, 0, sizeof(val));Map.clear();cnt = 0;
}int insert(int x)
{if (Map.find(x) == Map.end())//不存在这个数字Map[x] = cnt++;return Map[x];
}int main()
{while (cin >> n >> m){ini();int ans = m;for (int i = 0; i < m; i++){int a, b;//string str;char str[39];cin >> a >> b >> str;if (a > b)swap(a, b);if (ans < m)continue;//通过map来分配编号，是一个左开右闭区间，详细见hdu 3038a = insert(a - 1);b = insert(b);int flag;if (str[0] == 'e')//偶数flag = 0;else flag = 1;//奇数///cout << "a=" << a << " b=" << b << endl;int fa = find(a);int fb = find(b);if (fa == fb){if ((val[a] ^ val[b]) != flag)//如果这两段和给出的区间范围里的奇偶数是否一致，若不一致，则ans = i;}else{par[fb] = fa;val[fb] = flag ^ val[a] ^ val[b];}}cout << ans << endl;}return 0;
}

WA 的代码

#pragma warning(disable:4996)
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<ctype.h>
#include<memory.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
#define ll long long int
using namespace std;
const int maxn = 20000;int n, m;
int par[maxn];
int val[maxn];
map<int, int> Map;
int cnt = 0;int find(int x)//错误写法！
{if (par[x] == -1)return x;//不可以改为par[x]val[x] ^= val[par[x]];
//	cout<<"va[x]="<<val[x]<<" par[x]="<<par[x]<<" val[par[x]]="<<val[par[x]]<<endl;return par[x] = find(par[x]);
}
//int find(int x)
//{
//	if (par[x] == -1)return x;
//	int tmp = find(par[x]);
//	val[x] ^= val[par[x]];
//	return par[x] = tmp;
//}void ini()
{//for (int i = 0; i < n; i++)//{//	//par[i] = i;////	par[i] = -1;//	val[i] = 0;//}memset(par, -1, sizeof(par));memset(val, 0, sizeof(val));Map.clear();cnt = 0;
}int insert(int x)
{if (Map.find(x) == Map.end())//不存在这个数字Map[x] = cnt++;return Map[x];
}int main()
{while (cin >> n >> m){ini();int ans = m;for (int i = 0; i < m; i++){int a, b;//string str;char str[39];cin >> a >> b >> str;if (a > b)swap(a, b);if (ans < m)continue;//通过map来分配编号，是一个左开右闭区间，详细见hdu 3038a = insert(a - 1);b = insert(b);int flag;if (str[0] == 'e')//偶数flag = 0;else flag = 1;//奇数///cout << "a=" << a << " b=" << b << endl;int fa = find(a);int fb = find(b);if (fa == fb){if ((val[a] ^ val[b]) != flag)//如果这两段和给出的区间范围里的奇偶数是否一致，若不一致，则ans = i;}else{par[fb] = fa;val[fb] = flag ^ val[a] ^ val[b];}}cout << ans << endl;}return 0;
}