贸易公司网站制作,wordpress ip排行,怎么样才能建立网站平台,百度网站与推广小 A 旅行到了远方的一座城市#xff0c;其内部的道路可以被视为一张包含恰好 n n n 个点以及 n n n 条边的无向连通图。这里的居民可以用一种特质的墨水来改变图中某一条边的颜色。
居民们的狂欢节即将开始了#xff0c;且节日会持续 m m m 天。每一天#xff0c;居民们…小 A 旅行到了远方的一座城市其内部的道路可以被视为一张包含恰好 n n n 个点以及 n n n 条边的无向连通图。这里的居民可以用一种特质的墨水来改变图中某一条边的颜色。
居民们的狂欢节即将开始了且节日会持续 m m m 天。每一天居民们会选择图中的一条边并用某一种颜色的墨水去覆盖这条边原有的颜色。在每一天的最后他们都想知道当前的城市包含多少个颜色相同的连通块。
特别的一个颜色相同的连通块指的是一个由一些相同颜色的边组成的连通块。
多组数据 T ≤ 10 T\le10 T≤10 n , m ≤ 1 0 5 n,m\le10^5 n,m≤105 首先这个图是基环树。
可以用各种方法求出一开始颜色相同连通块的个数。我使用并查集。
对于每次询问改变这条边的颜色贡献只需看两个点的连边情况。
可以分成两部分考虑先去掉这条边的颜色再加上修改的颜色。
前一个操作如果两边都有这种颜色那么断掉这条边会增加一个连通块如果两边都没有就会减少一个否则不变。
后一个操作如果两边都有这种颜色那么断掉这条边会减少一个连通块如果两边都没有就会增加一个否则不变。
但是如果两边的颜色是同一个连通块那么就不会增加连通块这种情况只能是环上的边全是一种颜色在后种情况就是除了当前边全是一种颜色特判即可。
实现上可以开 n n n 个 map 维护当前点的出边颜色。
时间复杂度 O ( T n log n ) O(Tn\log n) O(Tnlogn)
代码如下
#includebits/stdc.h
using namespace std;
const int N2e51;
int n,m,fa[N],bj[N],dfn[N],low[N],num,vis[N],VIS[N];
stackint s;
vectorint ans;
mapint,int ma[N],ring;
mappairint,int,int To;
struct Node
{int v,w,id;Node(){}Node(int a,int b,int c){va,wb,idc;}
};
vectorNode v[N];
struct node
{int u,v,w;bool operator(const node a)const{return ua.uva.vwa.w;}
}a[N];
int find(int x)
{return xfa[x]?x:fa[x]find(fa[x]);
}
void add(int x,int y)
{int afind(x),bfind(y);if(a!b) fa[a]b;
}
void dfs(int u,int fa)
{dfn[u]low[u]num;s.push(u);for(auto i:v[u]){if(!dfn[i.v]){dfs(i.v,u);low[u]min(low[u],low[i.v]);if(low[i.v]dfn[u]){vectorint aa;int x0;do{xs.top();s.pop();aa.push_back(x);}while(x!i.v);aa.push_back(u);if(aa.size()2) ansaa;}}else if(i.v!fa) low[u]min(low[u],dfn[i.v]);}
}
void Dfs(int u,int fa)
{if(VIS[u]) return;VIS[u]1;for(auto i:v[u]) if(i.v!favis[i.v]) ring[i.w],Dfs(i.v,u);
}
int main()
{freopen(tour.in,r,stdin);freopen(tour.out,w,stdout);int t;cint;while(t--){memset(VIS,0,sizeof(VIS));memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));num0;while(s.size()) s.pop();To.clear();ans.clear();ring.clear();scanf(%d%d,n,m);for(int i1;in;i) fa[i]i;for(int i1,x,y,w;in;i){scanf(%d%d%d,a[i].u,a[i].v,a[i].w);if(a[i].ua[i].v) swap(a[i].u,a[i].v);v[a[i].u].push_back(Node(a[i].v,a[i].w,i));v[a[i].v].push_back(Node(a[i].u,a[i].w,i));ma[a[i].u][a[i].w];ma[a[i].v][a[i].w];To[make_pair(a[i].u,a[i].v)]i;}dfs(1,0);for(auto i:ans) vis[i]1;if(ans.size()) for(auto i:v[ans.front()]) if(vis[i.v]){Dfs(ans.front(),i.v);break;}for(int i1;in;i){for(auto j:v[a[i].u]){if(j.va[i].v) continue;if(j.wa[i].w) add(i,j.id);}for(auto j:v[a[i].v]){if(j.va[i].u) continue;if(j.wa[i].w) add(i,j.id);}}for(int i1;in;i) bj[i]find(i);sort(bj1,bj1n);int numunique(bj1,bj1n)-bj-1;for(int i1,x,y,w;im;i){scanf(%d%d%d,x,y,w);if(xy) swap(x,y);int idTo[make_pair(x,y)];int fl10,fl20;ma[a[id].u][a[id].w]--;ma[a[id].v][a[id].w]--;fl1ma[a[id].u][a[id].w];fl2ma[a[id].v][a[id].w];ma[a[id].u][a[id].w];ma[a[id].v][a[id].w];if(fl1fl2(!vis[a[id].u]||!vis[a[id].v]||ring.size()1)) num;else if(!fl1!fl2) num--;ma[a[id].u][a[id].w]--;ma[a[id].v][a[id].w]--;if(vis[a[id].u]vis[a[id].v]) ring[a[id].w]--;if(!ring.count(a[id].w)) ring.erase(a[id].w);if(!ma[a[id].u][a[id].w]) ma[a[id].u].erase(a[id].w);if(!ma[a[id].v][a[id].w]) ma[a[id].v].erase(a[id].w);a[id].ww;ma[a[id].u][a[id].w];ma[a[id].v][a[id].w];if(vis[a[id].u]vis[a[id].v]) ring[a[id].w];fl10,fl20;ma[a[id].u][a[id].w]--;ma[a[id].v][a[id].w]--;fl1ma[a[id].u][a[id].w];fl2ma[a[id].v][a[id].w];ma[a[id].u][a[id].w];ma[a[id].v][a[id].w];if(vis[a[id].u]vis[a[id].v]){ring[a[id].w]--;if(!ring.count(a[id].w)) ring.erase(a[id].w);}if(fl1fl2(!vis[a[id].u]||!vis[a[id].v]||ring.size()1)) num--;else if(!fl1!fl2) num;if(vis[a[id].u]vis[a[id].v]) ring[a[id].w];printf(%d\n,num);}for(int i1;in;i) v[i].clear(),ma[i].clear();}
}
