ZJU 3261 逆向考虑,并查集

发布时间:2016-12-10 12:59:17 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"ZJU 3261 逆向考虑,并查集",主要涉及到ZJU 3261 逆向考虑,并查集方面的内容,对于ZJU 3261 逆向考虑,并查集感兴趣的同学可以参考一下。

#include <iostream> #include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <set> #define M 10000 using namespace std; struct Node { int p; int x; }node[10010]; struct Op { int o,n; }op[50010]; int tun[20010],n,m,q,ans[50010]; int find(int p) { if(node[p].p<0) return p; return node[p].p=find(node[p].p); } void merge(int a,int b) { a=find(a); b=find(b); if(a>b) swap(a,b); if(a==b) return; if(node[a].x>=node[b].x) node[b].p=a; else node[a].p=b; } int main() { //freopen("in.txt","r",stdin); //freopen("out2.txt","w",stdout); int pri=0; while(cin>>n) { int i,j,k; char s[10]; set<int> st; for(i=0;i<n;i++) { cin>>node[i].x; node[i].p=-1; } cin>>m; for(i=0;i<m;i++) { cin>>j>>k; if(j>k) swap(j,k); tun[i]=j*M+k; } cin>>q; for(i=0;i<q;i++) { cin>>s; if(s[0]=='q') { op[i].o=0; cin>>op[i].n; } else { op[i].o=1; cin>>j>>k; if(j>k) swap(j,k); op[i].n=j*M+k; st.insert(op[i].n); } } for(i=0;i<m;i++) if(!st.count(tun[i])) { merge(tun[i]/M,tun[i]%M); } i=q; while(i--) { if(op[i].o) { merge(op[i].n/M,op[i].n%M); ans[i]=-2; } else { j=find(op[i].n); if(node[j].x<=node[op[i].n].x) ans[i]=-1; else ans[i]=j; } } if(pri) cout<<endl; pri=1; for(i=0;i<q;i++) if(ans[i]>=-1) cout<<ans[i]<<endl; } return 0; }

上一篇:EasyUI Tree+Asp.net实现权限树或目录树导航
下一篇:

相关文章

相关评论