P3452 [POI2007] BIU-Offices 题解
xcrr
·
·
题解
从直接搜索的角度优化。
题意
给 n 个点的完全图，给定 m 条边不能走，问连通块个数。
朴素
从朴素做法来想，直接广搜。
想其更新新点的流程（以下简称“流程”），是对于出队的点 u，找到它所有连边，如果连边对应的点没有被访问过，即没被 vis 数组标记，那么就将它进队。
复杂度 O(n+e) ，n 是点数，e 是边数。
过不了，只因这个题 e 与 n^2 同阶的特点。
优化
上面提到的流程是我们复杂度的瓶颈，想想在这个题下我们如何优化。
输入的边，代表在图中删掉了这条边。
因为大部分边都能走，就相当于 u 除了删掉的边对应的点外，其余 v=1 \to n 都可直达。
由于不能直达的点相对很少，
流程就变成了对于 u，扫一遍（除了被删的点，剩余的）整个 vis 数组，找到 vis 没有被标记的点，进入队列。
似乎很好优化了？用链表或并查集跳过 vis 标记过的点，不扫它们不就行了，均摊下来就 O(n) 了。
细节在于，如何处理扫 vis 数组时跳过被删的点？我们可以将每个点 u 预处理出可达区间，区间之间不包含的部分就是相对 u 而言删掉的点，也就是 u 出队时扫 vis 跳过的点。处理好这个，流程中，我们对每个区间分别做即可。
举个例子
若 n=100：
若加入 $u=1,v=5$，对 $1$ 号来说就是删掉了 $5$ 号，$1$ 号的可达区间变为 $[2,4],[6,100]$。
若再加入 $u=1,v=20$，$1$ 号的可达区间变为 $[2,4],[6,19],[21,100]$。
以此类推。注意上面只是拿 $1$ 号点举例。处理时要对每个点处理，比如对 $3$ 而言第一个读入就是删掉了 $1$。
这部分不是重点，但是可能有点抽象，可以直接读代码帮助理解。
```cpp
#define pr make_pair
int fa[N],c[N];
int getfa(int x){if(x>n)return x;return fa[x]==x?x:fa[x]=getfa(fa[x]);}
vector<int>G[N];//暂时存储删掉的边
vector<pair<int,int> >v[N];
int bfs(int x)
{
int ret=0;
queue<int>q;
q.push(x);
fa[x]=x+1;
while(q.size())
{
int nq=q.front(); q.pop();
ret++;
for(auto rg:v[nq])//对每个可达区间分别做
{
int l=rg.first,r=rg.second;
for(int i=getfa(l);i<=r;i=getfa(i))
q.push(i),fa[i]=i+1;
}
}
return ret;//返回连通块大小
}
inline void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)fa[i]=i,G[i].push_back(i);
for(int i=1,u,v;i<=m;i++)
cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
for(int i=1;i<=n;i++)//处理删边
{
sort(G[i].begin(),G[i].end());
int l=1;
for(auto cc:G[i])
{
if(l<=cc-1) v[i].push_back(pr(l,cc-1));
l=cc+1;
}
if(l<=n) v[i].push_back(pr(l,n));
}
vector<int>ans;
for(int i=1;i<=n;i=getfa(i))
ans.push_back(bfs(i));
cout<<ans.size()<<endl;
sort(ans.begin(),ans.end());
for(auto p:ans) cout<<p<<' ';
}
```