USACO22OPEN-Platinum D
前言(Front talk)
网址(Website)
题目(Problem)
输入格式(Input)
输出格式(Output)
样例(Example)
样例输入
9 10
1 2
2 3
3 4
4 7
3 5
1 6
6 8
8 9
9 6
7 2
4
1 5
1 2
1 6
2 4
样例输出
BHHB
提示(Notice)
【数据范围】
【测试点性质】
- 测试点 2-3 满足
, 。 - 测试点 4-9 满足
。 - 测试点 10-21 没有额外限制。
题解(Solution)
理清楚思路:
想清楚做法:
代码(Code)
#include<bits/stdc++.h>
#include<queue>
#include<set>
#define For(i,l,r) for(int i=l;i<=r;++i)
#define Rof(i,l,r) for(int i=l;i>=r;--i)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int N = 101234;
set<int> ft[N],tf[N];
int n,m,Q,inn[N];
int fa[N];
queue<int> q;
void bfs_dead(){
For(x,1,n) if(ft[x].size()==0) q.emplace(x);
For(i,1,n) fa[i]=i;
while(q.size()){
int x=q.front();q.pop();
fa[x]=0;//已经死的点没有爸爸
for(auto y:tf[x]){
ft[y].erase(x);
if(ft[y].empty()) q.emplace(y);
}
}
}
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void bfs_scc(){
For(x,1,n) if(ft[x].size()==1) q.emplace(x);
while(q.size()){
int x=q.front();q.pop();
int y=*ft[x].begin();
// cout<<x<<' '<<y<<' '<<q.front()<<'\n';
x=find(x),y=find(y);
if(x==y) continue;
if(tf[x].size()>tf[y].size()) swap(x,y);
for(auto i:tf[x]){
ft[i].erase(x);
ft[i].emplace(y);
tf[y].emplace(i);
if(ft[i].size()==1) q.emplace(i);
}fa[x]=y;
}
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
freopen("hoof.in", "r", stdin);
freopen("hoof.out", "w", stdout);
cin>>n>>m;For(i,1,m){
int x=input(),y=input();
ft[x].emplace(y);
tf[y].emplace(x);
}cin>>Q;
bfs_dead();
bfs_scc();
while(Q--){
int x=find(input()),y=find(input());
cout<<(!x || !y || x==y ? 'B' : 'H');
}return 0;
}
后续(Ending)
讲几个自已从来没有想到的点:
- 用
来支持建边和删边的操作,同时还有去重边的功能,之后在强连通分量中可以用到这个方法重建边。 - 合并路径的方法,我当时一直在想如何给一条必走路径上的点打标记,从来没有想到过合并两个点。
- 启发式合并的应用,因为每个点的边数不一样,直接合并会带来大量的时间消耗,因此用启发式合并+并查集,保证了时间复杂度的同时也解决了每一条必走路径的编号问题。