AGC027C – ABland Yard

发布于 2018-11-22  256 次阅读


题目描述

题目链接
给出一个 $N$ 个点、 $M$ 条边的无向图(节点编号 $1~N$ )。每个节点有一个值 A 或 B,你可以从任意一个节点出发,经过一些节点后(可以重复经过),你将经过的节点的值顺次写出来,就可以得到一个只包含 A 或 B 的字符串。求对于只包含 A 或 B 的字符串 $S$ 都找得到一个合法的访问序列使得得到的字符串恰好为 $S$ 。

题解

显然如果存在一个类似于 AABB 的环就可以满足所有的条件。于是题目变成了判断图里有没有这样的环。
这个结论证明很好证明:如果这个环里 A 或 B 的个数小于1,那么无法构成 AA 或 BB。
如果这个环里连续 A 或 B 的个数超过 2,则存在一个结尾为 ABBA 或 BAAB 无法构成。
我们判断可以类比拓扑排序的方法,将所有只与 A 或 B 相连的点删除,不断进行知道不能删除为止。
剩下的就一定是形如 AABB 的环了。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 200000+5;

struct Node{
    struct Edge *firstEdge;
    int d[2];bool vis;
    int num;
}node[MAXN];

struct Edge{
    Node *s,*t;
    Edge *next;
}pool[MAXN<<1],*frog = pool;

Edge *New(Node *s,Node *t){
    Edge *ret = ++frog;
    *ret = (Edge){s,t,s->firstEdge};
    return ret;
}

char str[MAXN];

inline void add(int u,int v){
    node[u].firstEdge = New(&node[u],&node[v]);
    ++node[u].d[str[v]-'A'];
}

int N,M;

int main(){
    scanf("%d%d",&N,&M);
    scanf("%s",str+1);
    FOR(i,1,N) node[i].num = i;
    FOR(i,1,M){
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    std::queue q;
    FOR(i,1,N) if(!node[i].d[0] || !node[i].d[1]) q.push(&node[i]),node[i].vis = true;
    int cnt = q.size();
    while(!q.empty()){
        Node *v = q.front();q.pop();
        for(Edge *e = v->firstEdge;e;e = e->next){
            if(!--e->t->d[str[v->num]-'A'] && !e->t->vis){
                q.push(e->t);cnt++;
                e->t->vis = true;
            }
        }
    }
    puts(cnt != N ? "Yes" : "No");
    return 0;
}



一个OIer。