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

贴代码:

#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学堂

为什么不要在 JavaScript 中使用位操作符?

如果你的第一门编程语言不是 JavaScript,而是 C++ 或 Java,那么一开始你大概会看不惯 JavaScript 的数字类型。在 JavaScrip...

34610
来自专栏cmazxiaoma的架构师之路

Java数据结构和算法(2)--《Java数据结构和算法》第二版 Robert lafore第二章【数组】编码作业

1543
来自专栏机器学习从入门到成神

数据库闭包和候选码求解方法

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

791
来自专栏nnngu

算法02 七大排序之:直接选择排序和堆排序

上一篇总结了交换排序的冒泡排序和快速排序。这一篇要总结的是选择排序,选择排序分为直接选择排序和堆排序,主要从以下几点进行总结。 1、直接选择排序及算法实现 2、...

3407
来自专栏于晓飞的专栏

读 Java TimSort算法 源码 笔记

本来准备看Java容器源码的。但是看到一开始发现Arrays这个类我不是很熟,就顺便把Arrays这个类给看了。Arrays类没有什么架构与难点,但Arrays...

692
来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

692
来自专栏编程

八大排序算法总结与java实现

概述 因为健忘,加上对各种排序算法理解不深刻,过段时间面对排序就蒙了。所以决定对我们常见的这几种排序算法进行统一总结。首先罗列一下常见的十大排序算法: ? 请点...

19910
来自专栏一个会写诗的程序员的博客

函数式编程与面向对象编程[1]: Lambda表达式 函数柯里化 高阶函数函数式编程与面向对象编程[1]: Lambda表达式 函数柯里化 高阶函数.md

For example, in Lisp the 'square' function can be expressed as a lambda expressi...

542
来自专栏Java Edge

二分查找复杂度分析实战演练

3328
来自专栏菩提树下的杨过

javascript:算法笔记

入门级算法-线性查找-时间复杂度O(n)--相当于算法界中的HelloWorld //线性搜索(入门HelloWorld) //A为数组,x为要...

16810

扫码关注云+社区