poj 1733(带权并查集+离散化)
题目链接：http://poj.org/problem?id=1733
思路：这题一看就想到要用并查集做了，不过一看数据这么大，感觉有点棘手，其实，我们仔细一想可以发现，我们需要记录的是出现过的节点到根节点的1个奇偶性，这与区间端点的大小并没有关系，于是想到我们可以用map映射即可，这样就解决了大数据了。此外，如果0表示出现偶数个1，1表示出现奇数个1，然后就是向量偏移关系了(http://www.cnblogs.com/wally/archive/2013/06/10/3130527.html).
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<map> 6 using namespace std; 7 #define MAXN 5050 8 9 int parent[MAXN]; 10 int kind[MAXN]; 11 int n,m,Index; 12 13 void Initiate() 14 { 15 for(int i=0;i<MAXN;i++){ 16 parent[i]=i; 17 } 18 memset(kind,0,sizeof(kind)); 19 } 20 21 int Find(int x) 22 { 23 if(x==parent[x]){ 24 return parent[x]; 25 } 26 int tmp=Find(parent[x]); 27 kind[x]=(kind[x]+kind[parent[x]])%2; 28 return parent[x]=tmp; 29 } 30 31 bool Union(int u,int v,int d) 32 { 33 int r1=Find(u),r2=Find(v); 34 if(r1==r2){ 35 if(kind[u]!=(kind[v]+d)%2)return false; 36 return true; 37 } 38 parent[r1]=r2; 39 kind[r1]=(kind[v]-kind[u]+d+2)%2; 40 return true; 41 } 42 43 int main() 44 { 45 int a,b,d,pos; 46 char str[11]; 47 while(~scanf("%d%d",&n,&m)){ 48 Index=0; 49 map<int,int>mp; 50 bool flag=true; 51 Initiate(); 52 for(int i=0;i<m;i++){ 53 scanf("%d%d%s",&a,&b,str); 54 d=(str[0]=='e'?0:1);a--; 55 if(mp.find(a)==mp.end()){ 56 mp[a]=Index++; 57 } 58 if(mp.find(b)==mp.end()){ 59 mp[b]=Index++; 60 } 61 if(!flag)continue; 62 if(!Union(mp[a],mp[b],d)){ 63 flag=false; 64 pos=i; 65 } 66 } 67 if(flag)pos=m; 68 printf("%d ",pos); 69 } 70 return 0; 71 } 72 73 74 75 76 77 78 79