拓扑排序 ——个人理解,仅供参考

贴代码:

#include <bits/stdc++.h>
using namespace std;
#define maxn 100//可以根据题目条件进行更改
int edge[maxn][maxn];
int book[maxn];
int point_num;
int edge_num;
bool check_point(int v)//确定这个点是不是没有入度;
{
    for(int i=1;i<=point_num;i++)
        if(edge[i][v]==1&&(i!=v))//如果有入度,返回false,i==v时没有啥实际意义
        return false;
    return true;
}
void del_edge(int v)//删除以这个点为起始点的所有边
{
    fill(edge[v],edge[v]+point_num,0);//fill灵活用法,用for循环效果一样,时间复杂度相同
}
int main()
{
    memset(book,0,sizeof(book));
    scanf("%d",&point_num);
    scanf("%d",&edge_num);//点的个数,边的个数,设为宏观变量,比较好操作
    memset(edge,0,sizeof(edge));
    
    for(int i=1;i<=edge_num;i++)
    {
        int s_point,e_point;
        scanf("%d%d",&s_point,&e_point);
        edge[s_point][e_point]=1;
    }
    int i;//下面循环代码肯定是能优化的,不过我一时半会想不起来,欢迎留言,私信我
    for(;i<=point_num;i++)
    {
        if(check_point(i)&&book[i]==0)
        {
            book[i]=1;
            cout<<i<<" ";
            del_edge(i);//删除bian
            i=1;
        }
    }
    for(int i=1;i<=point_num;i++)
    {
        if(book[i]==0)
            cout<<i<<endl;
    }//扫尾工作,最后可能会留下一个点;输出格式自己搞!
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HTML5学堂

轻松但深入的学习闭包原理 —— 曾让几乎所有JS新手痛恨的知识

HTML5学堂-码匠:这或许是你看过的,最浅显易懂的一篇关于闭包原理的讲解! 闭包的官方定义 官方定义:闭包是一个拥有许多变量和绑定了这些变量的环境的表达式(通...

3346
来自专栏大前端_Web

jsvascript—谜之this?

版权声明:本文为吴孔云博客原创文章,转载请注明出处并带上链接,谢谢。 https://blog.csdn.net/wkyseo/articl...

1074
来自专栏xingoo, 一个梦想做发明家的程序员

结构体的优化声明

声明一个结构体的时候,因为考虑到内存的对齐。例如,int型的变量,需要4个字节,那么它在存储的时候就需要在地址能够被4个字节整除的地方开始申请。 例如我们申请下...

16710
来自专栏架构之路

JavaScript的三种类型检测typeof , instanceof , toString比较

1.typeof typeof是js的一个操作符,在类型检测中,几乎没有任何用处。 typeof 返回一个表达式的数据类型的字符串,返回结果为javascrip...

2905
来自专栏Felix的技术分享

KMP子字符串查找算法

1506
来自专栏LuckQI

Redis初识~List命令

862
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版4.5节函数的逆向之coredump例子

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

402
来自专栏iOS开发攻城狮的集散地

浅谈iOS内存管理机制

1989
来自专栏技术/开源

从C#到TypeScript - 装饰器

从C#到TypeScript - 装饰器 在C#里面如果想要不直接修改类或方法,但给类或方法添加一些额外的信息或功能,可以想到用Attribute,这是一个十分...

20310
来自专栏PHP在线

PHP中正则表达式学习及应用

正则表达式元字符 * 匹配前一个内容的0次1次或多次 . 匹配内容的0次1次或多次,但不包含回车换行 + 匹配前一个内容的1次或多次 ?匹配前一个内容...

3078

扫码关注云+社区