首页 > 其他分享 >T397291 【模板】拓扑排序(加强版)

T397291 【模板】拓扑排序(加强版)

时间:2023-12-26 17:34:10浏览次数:34  
标签:加强版 int 入度 100005 T397291 模板

原题链接

思路

找到所有入度为零的点,然后消除其子节点的入度,再把入度为零的点塞入队列中

为什么可以这么做呢?
一个点能弹出队列,其父节点一定比他先入队,以此类推。。

代码

#include<bits/stdc++.h>
using namespace std;
vector<int> G[100005];
int in[100005]={0};
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        while(scanf("%d",&x)&&x!=0)
        {
            G[i].push_back(x);
            in[x]++;
        }
    }
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(!in[i]) q.push(i);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=0;i<G[now].size();i++)
        {
            int next=G[now][i];
            in[next]--;
            if(!in[next])q.push(next);
        }
        printf("%d ",now);
    }
    return 0;
}

标签:加强版,int,入度,100005,T397291,模板
From: https://www.cnblogs.com/pure4knowledge/p/17928882.html

相关文章

  • python .gitignore 文件模板 & 相关注意事项
    参考:https://blog.csdn.net/qq_38122800/article/details/132663030https://blog.csdn.net/weixin_42289273/article/details/122912938https://zhuanlan.zhihu.com/p/22494724在使用git进行代码版本管理时,对于不想提交的部分内容,可以通过.gitignore文件来配置提交时......
  • 如何使用ChatGPT快速构建一个网站模板
    圣诞狂欢,感恩有你......
  • NC65单据模板公式使用
    单据模板公式使用(一)公式使用场景用户使用产品时,往往对单据上的字段取值有各种不同的需求。为此单据模板提供了模板公式功能,可以让实施顾问或者用户通过配置各种公式,并且不用修改代码,从而满足用户的各种个性化需求。(二)单据模板三种公式1、编辑公式可实现单据编辑中字......
  • 树状数组模板
    单点修改,区间查询/区间修改,单点查询template<typenameT>structBIT{#ifndeflowbit#definelowbit(x)(x&(-x));#endif //staticconstintmaxn=5e5+50; intn; vector<T>t; BIT(){} BIT(int_n):n(_n){t.resize(_n+1);} BIT(int_n,vect......
  • Halon 模板匹配流程
    读取图片read_image灰度筛选threshold面积筛选select_shape分区connection膨胀(填充缝隙)dilation_circle勾画边缘(轮廓)gen_contour_region_xld建立轮廓模型create_scaled_shape_model_xld(Contours,‘auto’,rad(0),rad(360),‘auto’,0.8,1.1,‘auto’,‘auto’,‘......
  • Windows Server 2016 OVF, updated Dec 2023 (sysin) - VMware 虚拟机模板
    WindowsServer2016OVF,updatedDec2023(sysin)-VMware虚拟机模板2023年12月版本更新,现在自动运行sysprep,支持ESXiHostClient部署请访问原文链接:https://sysin.org/blog/windows-server-2016-ovf/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org现在......
  • Windows Server 2019 OVF, updated Dec 2023 (sysin) - VMware 虚拟机模板
    WindowsServer2019OVF,updatedDec2023(sysin)-VMware虚拟机模板2023年12月版本更新,现在自动运行sysprep,支持ESXiHostClient部署请访问原文链接:https://sysin.org/blog/windows-server-2019-ovf/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.orgWind......
  • Windows Server 2022 OVF, updated Dec 2023 (sysin) - VMware 虚拟机模板
    WindowsServer2022OVF,updatedDec2023(sysin)-VMware虚拟机模板2023年12月版本更新,现在自动运行sysprep,支持ESXiHostClient部署请访问原文链接:https://sysin.org/blog/windows-server-2022-ovf/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org现在......
  • lazy线段树模板
    importjava.io.*;importjava.util.*;publicclassMain{staticintN=(int)1e5+10;staticlong[]arr=newlong[N];staticlong[]sum=newlong[N<<2];staticlong[]lazy=newlong[N<<2];staticintn,m;public......
  • 揭秘JVS低代码平台:如何通过行内按钮逻辑引擎配置,实现高效文件模板替换下载
    在当今数字化的时代,各行各业都在寻求更高效、更便捷的工作方式。对于业务应用来说,将线下操作转化为线上流程是提升效率的关键。在业务应用中通常需要把行数据某字段赋值到一个文件模板上,用户下载该文件模板用于盖章或签字等线下操作。这样的场景在JVS低代码平台上可以通过行内按钮......