T2 [USACO22DEC] Making Friends P
考虑删除一个点,会有如下的点相连接:
题目要求如果两两个点建立联系,只会建立一次。所以,神奇地,我们取出当前待删的点所连接的最小的点,将它和剩下的点连接。手摸一下会发现这样就巧妙地给每个改建的边都建了一次。所以用一个 set 启发式合并就做完了,复杂度 \(O(n\log^2n)\)。应该没有人写线段树合并吧
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
putchar(sf);
}
constexpr int MAXN=2e5+5;
int n,m;
long long ans;
set<int>st[MAXN];
int main(){
n=read(),m=read();
for(int i=1,u,v;i<=m;++i){
u=read(),v=read();
if(u>v)swap(u,v);
st[u].emplace(v);
}
for(int i=1,t;i<=n;++i){
if(st[i].empty())continue;
ans+=st[i].size();
t=*st[i].begin(),st[i].erase(st[i].begin());
if(st[i].size()>st[t].size())swap(st[i],st[t]);
for(auto x:st[i])st[t].emplace(x);
}
write(ans-m);
return fw,0;
}
标签:int,题解,st,USACO22DEC,Making,Friends
From: https://www.cnblogs.com/laoshan-plus/p/18438247