自己做视频类网站用哪个cms,建设网站企业银行,前端网站开发项目经验,网站建设大赛策划书原题链接#xff1a;码题集OJ-我会修改图
题目大意#xff1a;给你一张n个点#xff08;编号为1∼n#xff09;#xff0c;m条边#xff08;编号为1∼m#xff09;的无向图#xff0c;图上每个点都有一个点权#xff0c;权值分别为a1,a2,…,an码题集OJ-我会修改图
题目大意给你一张n个点编号为1∼nm条边编号为1∼m的无向图图上每个点都有一个点权权值分别为a1,a2,…,an你需要支持以下询问或操作总共有q次。
1 x把编号为x(1≤x≤m)的边删除。
2 x y询问从点x(1≤x≤n)出发能够到达多少个不同的点t(t!x)满足axaty。
思路因为操作二需要找到与当前点连接的符合条件的点所以可以很自然的想到并查集但是操作一会导致并查集的图断开并且并查集这个算法不能很好的分离出点。正难则反如果记录每一个操作并且倒序的进行对于操作二查询并不会出错对于操作一并查集可以很好的将二个不连通的图联通。但是仍然会超时因为数据很大所以需要加快操作二查询有效点的速度可以开一个map数组代表以某个点为根的并查集中的数的总数。
//冷静冷静冷静
//调不出来就重构
#pragma GCC optimize(2)
#pragma GCC optimize(O3)
#includebits/stdc.h
#define endl \n
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pairll,ll pii;
const int N4e510,mod1000000007;
ll fa[N];//并查集的数组
ll p[N];//每个点的权值
pii op[N];//建立的边
bool st[N];//删除的边
struct node
{ll cz;//操作的类型是删除边还是求符合条件的点 ll a;//如果是删除边这个就是边的序号如果是求点这就是点的编号 ll b;//先加得到得值
}kp[N];
mapll,ll cnt[N];//例如cnt[2]就是以2为首得并查集里面所有数得集合cnt[2][1]就是以2为首的并查集中1的个数
ll find(ll x)
{if(xfa[x])return x;return fa[x]find(fa[x]);
}
void hb(pii v)
{ll xv.first,yv.second;xfind(x);yfind(y);if(xy)return;if(cnt[x].size()cnt[y].size())swap(x,y);fa[x]y;for(auto vb:cnt[x])//因为合并了那么就要将二个并查集中的数字数量也合并对于这种情况将小的并查集合并到大的并查集中 {cnt[y][vb.first]vb.second;}
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll n,m,q;cinnmq;for(int i1;in;i){cinp[i];fa[i]i;cnt[i][p[i]];}for(int i1;im;i){cinop[i].firstop[i].second;}for(int i1;iq;i){cinkp[i].cz;if(kp[i].cz1){cinkp[i].a;st[kp[i].a]1; }else{cinkp[i].akp[i].b;}}for(int i1;im;i)//建立最终的并查集{if(st[i])continue;hb(op[i]);}vectorll ans;for(int iq;i;i--){if(kp[i].cz1)//相反的操作最终合成出最初的并查集 {ll vkp[i].a;hb(op[v]);}else{ll xkp[i].a,ykp[i].b;ll vp[x];xfind(x);ans.push_back(cnt[x][y-v]-(y-vv));//题目要求不能和自己 }}for(int ians.size()-1;i0;i--)coutans[i]endl; return 0;
}
