知足且坚定 温柔且上进
Decayed Bridges
题目描述
There are N islands and M bridges.
The i-th bridge connects the Ai-th and Bi-th islands bidirectionally.
Initially, we can travel between any two islands using some of these bridges.
However, the results of a survey show that these bridges will all collapse because of aging, in the order from the first bridge to the M-th bridge.
Let the inconvenience be the number of pairs of islands (a,b) (a<b) such that we are no longer able to travel between the a-th and b-th islands using some of the bridges remaining.
For each i (1≤i≤M), find the inconvenience just after the i-th bridge collapses.
Constraints
All values in input are integers.
·2≤N≤105
·1≤M≤105
·1≤Ai<Bi≤N
·All pairs (Ai,Bi) are distinct.
·The inconvenience is initially 0.
输入
Input is given from Standard Input in the following format:
N M
A1 B1
A2 B2
⋮
AM BM
输出
In the order i=1,2,…,M, print the inconvenience just after the i-th bridge collapses. Note that the answer may not fit into a 32-bit integer type.
样例输入 Copy
4 5
1 2
3 4
1 3
2 3
1 4
样例输出 Copy
0
0
4
5
6
提示
For example, when the first to third bridges have collapsed, the inconvenience is 4 since we can no longer travel between the pairs (1,2),(1,3),(2,4) and (3,4).
题意： 起初给你一张无向图，然后按照给定的顺序删边，问每删一次边会造成多少损失（损失即不联通的两个点）
思路： 正着写是不好写的，我们不妨反过来考虑。假设一开始所有点都是孤立的，我把删边看成是添边，倒着加边，然后用并查集维护一下联通块的个数，就很轻松推出来了。
最开始所有点都是孤立的，损失的总数为n*(n-1)/2。因为首先从n个点里选1个点，有n种选法，再从剩下的n-1个点里选1个点，有n-1种选法，根据乘法原理，是n*(n-1).那么又因为（a,b）和（b,a）是一样的，所以要/2以去重。
我们每加一条边，都更新一下损失和各联通块内点的数量，每次损失增加的量即是cnt[x]*cnt[y]原理跟上面类似的~
不会并查集维护联通块的先看这个题~837. 连通块中点的数量 - AcWing题库
837代码：
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; //cnt[]表示祖宗节点所在集合中点的个数 int root[N],cnt[N]; int ffind(int x){ return root[x] == x ? x : root[x] = ffind(root[x]); } void uunion(int a,int b){ int x = ffind(a),y = ffind(b); if(x != y){ cnt[y] += cnt[x]; root[x] = y; } } int main(){ int n,m; cin>>n>>m; for(int i = 1; i <= n; i++) root[i] = i, cnt[i] = 1; while(m--){ char oper[2]; int x,y; scanf("%s",oper); if(oper[0] == 'C'){ cin>>x>>y; uunion(x,y); } else if(oper[1] == '1'){ cin>>x>>y; if(ffind(x) == ffind(y)) cout<<"Yes"<<endl; else cout<<"No"<<endl; } else{ cin>>x; cout<<cnt[ffind(x)]<<endl; } } return 0; }
本题代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; #define I_int ll inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } const int maxn=1e6+7; ll n,m; ll a[maxn],b[maxn]; ll root[maxn],cnt[maxn],tot[maxn]; ll res,ans=0; ll Find(ll x){ if(x==root[x]) return root[x]; else return root[x]=Find(root[x]); } void Union(ll a,ll b){ ll x=Find(a),y=Find(b); if(x!=y){ ans+=cnt[x]*cnt[y]; cnt[x]+=cnt[y]; root[y]=x; } } void init(){ for(ll i=1;i<=n;i++) root[i]=i,cnt[i]=1;///并查集 } void AC(){ n=read();m=read(); for(ll i=1;i<=m;i++){ a[i]=read(); b[i]=read(); } init(); res=n*(n-1)/2; for(ll i=m;i;i--){ tot[i]=res-ans; Union(a[i],b[i]); //cout<<i<<" "<<ans<<endl; } for(ll i=1;i<=m;i++) printf("%lld\n",tot[i]); } int main(){ AC(); return 0; }
这个题的逆向思维还是很好的~
