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

贴代码:

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

相关文章

来自专栏张善友的专栏

LINQ via C# 系列文章

LINQ via C# Recently I am giving a series of talk on LINQ. the name “LINQ via C...

3025
来自专栏杨龙飞前端

scrollto 到指定位置

2964
来自专栏芋道源码1024

熔断器 Hystrix 源码解析 —— 断路器 HystrixCircuitBreaker

本文主要基于 Hystrix 1.5.X 版本 1. 概述 2. HystrixCircuitBreaker 3. HystrixCircuitBreaker....

5827
来自专栏大内老A

The .NET of Tomorrow

Ed Charbeneau(http://developer.telerik.com/featured/the-net-of-tomorrow/) Exciti...

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

Flash/Flex学习笔记(23):运动学原理

先写一个公用的小球类Ball: package{ import flash.display.Sprite; //小球 类 public class B...

27410
来自专栏一个爱瞎折腾的程序猿

sqlserver使用存储过程跟踪SQL

USE [master] GO /****** Object: StoredProcedure [dbo].[sp_perfworkload_trace_s...

2970
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

7306
来自专栏我和未来有约会

Silverlight第三方控件专题

这里我收集整理了目前网上silverlight第三方控件的专题,若果有所遗漏请告知我一下。 名称 简介 截图 telerik 商 RadC...

4405
来自专栏我和未来有约会

Kit 3D 更新

Kit3D is a 3D graphics engine written for Microsoft Silverlight. Kit3D was inita...

2936
来自专栏张善友的专栏

Mix 10 上的asp.net mvc 2的相关Session

Beyond File | New Company: From Cheesy Sample to Social Platform Scott Hansel...

2787

扫码关注云+社区