#离散，并查集#JZOJ1375（初中）1779（高中）奇偶游戏poj1733codevs2546paritygame

首先用s数组来表示这个01序列从第一个开始到第i个的奇偶性。
a b even说明s[b]和s[a-1]的奇偶性相同&＃xff0c;否则不同。
当a b even且s[b]和s[a-1]的奇偶性不同或a b odd且s[b]和s[a-1]的奇偶性相同时为错误信息。
离散化&＃43;并查集。

#include
#include
using namespace std;
int len,n,p[10001],b[10001],f[10001],x[10001],y[10001],s[10001];
int bs(int u){int l&＃61;1,r&＃61;len,mid;while (l<&＃61;r){mid&＃61;(l&＃43;r)>>1;if (u&＃61;&＃61;p[mid]) return mid;if (u>p[mid]) l&＃61;mid&＃43;1; else r&＃61;mid-1;}
}
int getf(int u){if (f[u]&＃61;&＃61;u) return u;int y&＃61;getf(f[u]);s[u]&＃61;(s[f[u]]&＃43;s[u])&1;//改变奇偶return f[u]&＃61;y;
}
void uni(int i){s[f[x[i]]]&＃61;(s[x[i]]&＃43;b[i])&1;//存储奇偶f[f[x[i]]]&＃61;y[i];//合并
}
int main(){scanf("%*d%d",&n);for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){char t; scanf("%d%d %c",&x[i],&y[i],&t);if (t&＃61;&＃61;&＃39;o&＃39;) b[i]&＃61;1; while (getchar()!&＃61;&＃39;\n&＃39;);//标记奇数&＃xff08;/2余数为1&＃xff09;p[(i<<1)-1]&＃61;--x[i]; p[i<<1]&＃61;y[i]; //存储前面的地址和后面的地址} stable_sort(p&＃43;1,p&＃43;1&＃43;2*n); p[0]&＃61;1; for (int i&＃61;2;i<&＃61;2*n;i&＃43;&＃43;) //快排并去重if (p[i]!&＃61;p[p[0]]) p[&＃43;&＃43;p[0]]&＃61;p[i]; len&＃61;p[0];for (int i&＃61;1;i<&＃61;len;i&＃43;&＃43;) f[i]&＃61;i;for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){x[i]&＃61;bs(x[i]); y[i]&＃61;bs(y[i]);//二分查找if (getf(x[i])&＃61;&＃61;getf(y[i])){//之前有信息证明if (((s[x[i]]&＃43;s[y[i]])&1)!&＃61;b[i]) {printf("%d",i-1);return 0;}}//奇偶性不同else uni(i);}printf("%d",n);return 0;
}