AGC027 C. ABland Yard
Difficulty:2077
問題文
#AGC027 #AGC
#BFS
問題
N頂点M辺のグラフがある。頂点にはAかBが書いてある。任意の頂点から任意の回数辺を使って移動することで、通った文字列を獲得できる。ABからなる任意の文字列を獲得できるか？
解法
Aが書いてあるような頂点とBが書いてある頂点のどちらにも移動できる頂点のみを使うことがわかる。よって、そうでない頂点を消していって、そのような頂点を残した場合、残った頂点たちで移動すれば任意の順番の文字列を作成できる。幅優先探索みたいな感じでやればよい。
実装
提出コード
code:cpp
bool solve(){
LL(n,m);
STR(s);
vector cnt(n,vector(2,0));
vector<vector<ll>>g(n);
rep(i,m){
LL(a,b);
a--,b--;
ga.push_back(b);
gb.push_back(a);
cnta[sb-'A']++;
cntb[sa-'A']++;
}
vector<ll>used(n,false);
queue<ll>q;
auto f = &(ll x){
if(cntx0==0||cntx1==0){
q.push(x);
usedx = 1;
}
return;
};
rep(i,n){
f(i);
}
while(q.size()){
ll pos = q.front();q.pop();
for(auto to:gpos){
if(usedto)continue;
cntto[spos-'A']--;
f(to);
}
}
if(sum(used)<n){
O("Yes");
}
else{
O("No");
}
return true;
}