汕头市网站建设公司,网站 微信小程序怎么做,中国网通,网站是否被k题目大意
有一个有 n n n个点 n n n条边的无向连通图#xff0c;一开始每条边都有一个颜色 c c c。
有 m m m次操作#xff0c;每次操作将一条两个端点为 x , y x,y x,y的边的颜色修改为 c c c。求每次修改之后#xff0c;图中有多少个颜色相同的连通块。
一个颜色相同的…题目大意
有一个有 n n n个点 n n n条边的无向连通图一开始每条边都有一个颜色 c c c。
有 m m m次操作每次操作将一条两个端点为 x , y x,y x,y的边的颜色修改为 c c c。求每次修改之后图中有多少个颜色相同的连通块。
一个颜色相同的连通块指的是一个由一些相同颜色的边组成的连通块。
有 T T T组数据。 1 ≤ T ≤ 10 , 3 ≤ n , m ≤ 1 0 5 , 1 ≤ c ≤ n 1\leq T\leq 10,3\leq n,m\leq 10^5,1\leq c\leq n 1≤T≤10,3≤n,m≤105,1≤c≤n 题解
我们可以发现这个图是一个基环树。
下面先考虑这个图是一棵树的情况。
我们考虑将一条边的修改看成给这条边删去颜色和给这条边加上颜色两个部分那么一开始加边时处理边的颜色也可以看作给没有颜色的边加上颜色。
我们先考虑删去一条边的颜色对答案的贡献设这条边的两个端点为 x , y x,y x,y颜色为 c c c
如果 x x x有另外一条颜色为 c c c的边 y y y也有则删去这条边后原本的这个连通块会变成两个连通块答案加一如果 x x x有另外一条颜色为 c c c的边 y y y没有则删去这条边后原本的这个连通块会少一个点 x x x答案不变如果 x x x没有另外一条颜色为 c c c的边 y y y有则删去这条边后原本的这个连通块会少一个点 y y y答案不变如果 x x x没有另外一条颜色为 c c c的边 y y y也没有则删去这条边后这个只由 x x x和 y y y构成的连通块就没了答案减一
再考虑加上一条边的颜色对答案的贡献设这条边的两个端点为 x , y x,y x,y颜色为 c c c
如果 x x x有另外一条颜色为 c c c的边 y y y也有则加上这条边后原本的这两个连通块会变成一个连通块答案减一如果 x x x有另外一条颜色为 c c c的边 y y y没有则加上这条边后原本的这个连通块会多一个点 y y y答案不变如果 x x x没有另外一条颜色为 c c c的边 y y y有则加上这条边后原本的这个连通块会多一个点 x x x答案不变如果 x x x没有另外一条颜色为 c c c的边 y y y也没有则加上这条边后就会构成一个只由 x x x和 y y y构成的连通块答案加一
而当这个图是基环树的时候有一些特殊情况需要特判
如果边在环上且环上的边的颜色都是 c c c则删去这条边后答案不变如果边在环上且环上除了这条边之外的边的颜色都是 c c c则加上这条边后答案不变
我们先找出环然后按上面说的做就可以了。
注意在查找两个端点为 x , y x,y x,y的边的编号和每个点是否有每种颜色的边的时候可以用 m a p map map来储存。
时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)。
code
#includebits/stdc.h
using namespace std;
const int N100000;
int T,n,m,tot,d[2*N5],l[2*N5],r[N5],c[N5];
int ans,top,st[N5],lp[N5],dep[N5],z[N5],sum[N5];
mapint,intmp[N5],hv[N5];
struct node{int x,y,v;
}w[N5];
void add(int xx,int yy){l[tot]r[xx];d[tot]yy;r[xx]tot;
}
void dfs(int u,int fa){dep[u]dep[fa]1;st[top]u;for(int ir[u];i;il[i]){if(d[i]fa) continue;if(dep[d[i]]dep[d[i]]dep[u]){while(st[top]!d[i]){lp[lp[0]]st[top];--top;}lp[lp[0]]d[i];}if(!dep[d[i]]) dfs(d[i],u);}if(st[top]u) --top;
}
void pt(int x,int y,int v,int zt){int tmp(hv[x][v]!0)(hv[y][v]!0);hv[x][v];hv[y][v];if(zt) sum[v];if(ztsum[v]lp[0]) --tmp;ans1-tmp;
}
void del(int x,int y,int v,int zt){--hv[x][v];--hv[y][v];int tmp(hv[x][v]!0)(hv[y][v]!0);if(ztsum[v]lp[0]) --tmp;if(zt) --sum[v];ans-1-tmp;
}
int main()
{freopen(tour.in,r,stdin);freopen(tour.out,w,stdout);scanf(%d,T);while(T--){scanf(%d%d,n,m);tot0;ans0;for(int i0;iN;i){r[i]dep[i]z[i]c[i]sum[i]0;mp[i].clear();hv[i].clear();}for(int i1,x,y,v;in;i){scanf(%d%d%d,x,y,v);w[i](node){x,y,v};add(x,y);add(y,x);mp[x][y]mp[y][x]i;}top0;lp[0]0;dfs(1,0);for(int i1,x,y;ilp[0];i){xlp[i];ylp[i%lp[0]1];z[mp[x][y]]1;}for(int i1;in;i){pt(w[i].x,w[i].y,w[i].v,z[i]);c[i]w[i].v;}for(int i1,x,y,v,p;im;i){scanf(%d%d%d,x,y,v);pmp[x][y];del(x,y,c[p],z[p]);pt(x,y,v,z[p]);c[p]v;printf(%d\n,ans);}}return 0;
}
