【抽象拓扑排序】ABC216 D

偏执的太偏执、 2024-03-17 16:01 47阅读 0赞

[D - Pair of Balls (atcoder.jp)][D - Pair of Balls _atcoder.jp]

题意：

有2\*n个球，每个球涂n种颜色，每种颜色恰好涂两个球，把这些球放进m个栈里，每次操作可以弹出两个相同颜色的球，问是否存在方案使得将所有栈清空

![b8087bed5398482b86b5776ac0692a46.png][]

思路：

注意到，对于上下两层的球是有有向约束关系的，即上面那个球弹出之后下面那个球才能弹出

**对于这种有向的约束关系，一个很好的想法是建有向图**

对于这道题，上下两层建一条有向边，然后做一遍拓扑排序即可，如果不存在环，那么就说明有解，否则就是无解

Code：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=4e5+5;
    int e[maxn],h[maxn],nex[maxn],id;
    int ans,in[maxn];
    queue<int>q;
    void add(int x,int y){
        e[++id]=y;
        nex[id]=h[x];
        h[x]=id;
    }
    int main(){
        int n,m;
        cin>>n>>m;
        for(int j=1;j<=m;j++){
            int k,pre,x;
            cin>>k>>pre;
            for(int i=2;i<=k;i++){
                cin>>x;
                add(x,pre);
                in[pre]++;
    			pre=x;
            }
        }
        for(int i=1;i<=n;i++){
            if(in[i]==0)q.push(i);
        }
    
        while(q.size()){
            int top=q.front();
            q.pop();
            ans++;
            for(int i=h[top];i;i=nex[i]){
                int j=e[i];
                in[j]--;
                if(in[j]==0)q.push(j);
            }
        }
        if(ans==n)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }

[D - Pair of Balls _atcoder.jp]: https://atcoder.jp/contests/abc216/tasks/abc216_d
[b8087bed5398482b86b5776ac0692a46.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ba69dc3e92224e1b97b988be684180c0.png

发表评论取消回复

表情：

评论列表（有 0 条评论，47人围观）

还没有评论，来说两句吧...

相关阅读

相关【排序+背包求方案数】ABC216 F

[F - Max Sum Counting (atcoder.jp)][F - Max Sum Counting _atcoder.jp] 题意： ![0ad34ab47c

谁借莪１个温暖的怀抱￠/ 2024年03月17日 16:03/ 0 赞/ 80 阅读

相关【贪心+推式子计算贡献】ABC216 E

[E - Amusement Park (atcoder.jp)][E - Amusement Park _atcoder.jp] 题意： ![578018ad8dee42

妖狐艹你老母/ 2024年03月17日 16:02/ 0 赞/ 59 阅读

相关【抽象拓扑排序】ABC216 D

[D - Pair of Balls (atcoder.jp)][D - Pair of Balls _atcoder.jp] 题意：有2\n个球，每个球涂n种颜色，每种

偏执的太偏执、/ 2024年03月17日 16:01/ 0 赞/ 48 阅读

相关【反图+拓扑排序】ABC245 F

[F - Endless Walk (atcoder.jp)][F - Endless Walk _atcoder.jp] 题意： ![d16bb1668bd54708a8

港控/mmm°/ 2024年03月17日 14:42/ 0 赞/ 79 阅读

相关拓扑排序

什么是拓扑排序? 在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序

冷不防/ 2022年06月09日 05:57/ 0 赞/ 232 阅读

相关拓扑排序

拓扑排序一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就

小鱼儿/ 2022年04月10日 08:23/ 0 赞/ 257 阅读

相关抽象基类（ABC）

抽象基类（ABC）文章目录抽象基类（ABC）前言如何实现ABC 为什么需要ABC 其他

灰太狼/ 2022年03月21日 17:49/ 0 赞/ 261 阅读

相关拓扑排序

（1）有向无环图无环的有向图，简称 DAG (Directed Acycline Graph) 图。有向无环图在工程计划和管理方面的应用：除最简单的情况之外，几

古城微笑少年丶/ 2022年03月18日 12:35/ 0 赞/ 300 阅读

相关拓扑排序

拓扑排序：拓扑排序是根据离散数学中有关偏序与全序定义的。 ![0_1314168765l7fq.gif][] 若一个集合 X 上的关系 R 是自反的反

淩亂°似流年/ 2021年12月23日 02:43/ 0 赞/ 356 阅读

相关拓扑排序

一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程

野性酷女/ 2021年09月19日 05:04/ 0 赞/ 465 阅读