算法复习 - AcWing - 数据结构

237. 程序自动分析

一开始用种类并查集调了半天，，，但是这并不是要分为两类啊喂！

A!=B, B!=C 不能推出A=C

因为是离线，正确的思路： （0）数据太大，离散化 （1）先把已知的相等情况处理完 （2）对于不相等的情况，如果他们已经在同一个并查集里，则出错

int f[MX]; vector<pair<int,pair<int,int>>>v; int find(int x) { return x==f[x]?x:f[x]=find(f[x]); } void solve() { int n;cin>>n; v.clear(); vector<int>tmp; rpp(i,n) { int x,y,z;cin>>x>>y>>z; v.push_back(make_pair(1-z,make_pair(x,y))); tmp.push_back(x),tmp.push_back(y); } map<int,int>id; int cnt=0; for(auto x:tmp) { if(id[x]) continue; id[x]=++cnt; } n=cnt; sort(all(v)); int flag=0; rpp(i,n) f[i]=i; for(auto op:v) { int x=id[op.second.first],y=id[op.second.second],z=op.first; int fx=find(x),fy=find(y); if(z==0) f[fx]=fy; else if(fx==fy) {flag=1;break;} } if(!flag) cout<<"YES\n"; else cout<<"NO\n"; }

239. 奇偶游戏（种类并查集，前缀和）

01串，考虑前缀和 告诉我们[l ~ r] 1的个数奇偶，相当于只告诉我们区间和奇偶，即前缀和S[l-1] 和 S[r]的奇偶关系也可以知道，转换为奇偶两类的种类并查集

//偶数个1：S[l-1] = S[r] //奇数个1：S[l-1] != S[r] int f[MX]; int tag[MX];//当前节点和根节点的关系,0表示相等.1表示不相等 vector<pair<pair<int,int>,int>>v; int find(int x) { if(x==f[x]) return x; else { int tmp=find(f[x]); tag[x]=(tag[x]+tag[f[x]])%2; return f[x]=tmp; } } void solve() { int n,m;cin>>n>>m; v.clear(); vector<int>tmp; rpp(i,m) { int x,y,z;string s;cin>>x>>y>>s; z=(s=="even"?0:1); --x; v.push_back(make_pair(make_pair(x,y),z)); tmp.push_back(x),tmp.push_back(y); } map<int,int>id; int cnt=0; for(auto x:tmp) { if(id[x]) continue; id[x]=++cnt; } n=cnt; rpp(i,n) f[i]=i,tag[i]=0; int pos=0,now=0; for(auto op:v) { ++now; int x=id[op.first.first],y=id[op.first.second],z=op.second; int fx=find(x),fy=find(y); if(fx==fy) { if((tag[x]^tag[y])!=z) { pos=now-1; break; } } else tag[fy]=(z+tag[x]+tag[y])%2,f[fy] = fx; } if(pos<=0) pos=m; cout<<pos<<endl; }

238. 银河英雄传说

调了好久，，菜菜菜 种类并查集维护的tag就是到***当前父亲节点的距离，在路径压缩的过程中，因为节点的父亲节点改变了，所以需要动态维护***一下，写这个题终于搞懂了！

int f[MX],tag[MX],ls[MX];//到根节点的距离,最后一个元素 int find(int x) { if(x==f[x]) return x; int tmp=find(f[x]); tag[x]=tag[f[x]]+tag[x]; return f[x] = tmp; } void solve() { rpp(i,30000) f[i]=i,tag[i]=0,ls[i]=i; int t;cin>>t; while(t--) { string op;int x,y;cin>>op>>x>>y; int fx=find(x),fy=find(y); if(op=="M") { if(fx!=fy) { f[fx]=ls[fy]; tag[fx]=1; ls[fy]=ls[fx]; } } else cout<<(fx==fy?abs(tag[x]-tag[y])-1:-1)<<endl; } } signed main() { fast;//不关流会T int T = 1; while (T--) solve(); return 0; }