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

贴代码:

#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 条评论
登录 后参与评论

相关文章

来自专栏企鹅号快讯

R包系列——stringr包

stringr包是Hadley Wickham大神贡献的R包之一,主要用于字符串的处理。对于经常需要对数据进行预处理的分析人员来说,简直是一把“利器”,可谓是上...

3356
来自专栏nice_每一天

转载 Java设计模式

设计模式; 一个程序员对设计模式的理解: “不懂”为什么要把很简单的东西搞得那么复杂。后来随着软件开发经验的增加才开始明白我所看到的“复杂”恰恰就是设计模式的精...

1252
来自专栏C语言及其他语言

【每日一题】问题 1209: 密码截获

Catcher是MCA国的情报员,他工作时发现敌国会用一些对称的密码 进行通信,比如像这些ABBA,ABA,A,123321,但是他们有时会在开始或结束时加入一...

1572
来自专栏逆向技术

win32编程简介

  我们要编写windos程序.都离不开API. 也就是我们所说的win32程序. 所以学好win32是你能不能再windows下编写程序的基础.

2803
来自专栏Lambda

Java8新日期处理API

Java8引入了一套全新的时间日期API,本篇随笔将说明学习java8的这套API。 java.time包中的是类是不可变且线程安全的。新的时间及日期API位...

47110
来自专栏程序员的酒和故事

跟Google学写代码--Chromium工程中用到的C++11特性

Ttile 跟Google学写代码--Chromium工程中用到的C++11特性 Chromium是一个伟大的、庞大的开源工程,很多值得我们学习的地方。 《跟...

4624
来自专栏项勇

笔记45 | 代码性能优化建议[转]

1406
来自专栏C语言及其他语言

[每日一题]C语言程序设计教程(第三版)课后习题4.9

题目描述 输入一个华氏温度,要求输出摄氏温度。公式为 c=5(F-32)/9 输出要求有文字说明,取位2小数。 输入 一个华氏温度,浮点数 输出 摄氏温度,浮点...

3096
来自专栏JMCui

Swagger文档转Word 文档

GitHub 地址:https://github.com/JMCuixy/SwaggerToWord/tree/developer 一、前言     为什么会产...

7218
来自专栏java一日一条

在Java中如何避免“!=null”式的判空语句?

我整天都是在跟Java打交道。我在Java开发中最常用的一段代码就是用object != null在使用对象之前判断是否为空。这么做是为了避免NullPoint...

2511

扫码关注云+社区

领取腾讯云代金券