首页 > 代码库 > zoj3261变形并查集
zoj3261变形并查集
需要变形的并查集,这题错了好久,一直没a掉,终于在重写第三次的时候a了
先保存数据,把不需要拆分的边合并,逆向计算,需要拆分时就合并,之前不知道为啥写搓了,tle好久
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define mod 100000000 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define MIN(a,b) a<b ? a:b #pragma comment(linker,"/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-9; const int N=10000+10,maxn=500+10,inf=40000000; int father[N],power[N]; vector<pair<int,int> >vec; vector<int>v[N]; stack<int>s; int Find(int x) { return x!=father[x] ? Find(x=father[x]) : x; } void Merge(int x,int y) { int fx=Find(x); int fy=Find(y); if(power[fx]>power[fy])father[fy]=fx; else if(power[fx]<power[fy])father[fx]=fy; else { if(fx<fy)father[fy]=fx; else father[fx]=fy; } } int main() { /* ios::sync_with_stdio(false); cin.tie(0);*/ int n,m,k,c=0; while(~scanf("%d",&n)){ if(c++)puts(""); for(int i=0;i<n;i++) { scanf("%d",&power[i]); v[i].clear(); father[i]=i; } vec.clear(); scanf("%d",&m); for(int i=0;i<m;i++) { int a,b; scanf("%d%d",&a,&b); if(a>b)swap(a,b); v[a].push_back(b); } scanf("%d",&k); while(k--){ char p[10]; scanf("%s",&p); if(p[0]==‘d‘) { int a,b; scanf("%d%d",&a,&b); if(a>b)swap(a,b); for(int i=0;i<v[a].size();i++) if(v[a][i]==b) v[a][i]=-1; vec.push_back(make_pair(a,b)); } else { int a; scanf("%d",&a); vec.push_back(make_pair(-1,a)); } } for(int i=0;i<n;i++) for(int j=0;j<v[i].size();j++) if(v[i][j]!=-1) Merge(i,v[i][j]); for(int i=vec.size()-1;i>=0;i--) { if(vec[i].first==-1) { int ans=Find(vec[i].second); if(power[ans]>power[vec[i].second])s.push(ans); else s.push(-1); } else Merge(vec[i].first,vec[i].second); } while(!s.empty()){ printf("%d\n",s.top()); s.pop(); } } return 0; }
zoj3261变形并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。