| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1403 人关注过本帖
标题:拓补排序
只看楼主 加入收藏
Jason_
Rank: 2
来 自:浙江台州
等 级:论坛游民
帖 子:88
专家分:66
注 册:2019-7-14
结帖率:66.67%
收藏
 问题点数:0 回复次数:1 
拓补排序
题目描述
给出n个点(n<=1000)给出m条有向边(m<=1000);按照拓扑排序顺序输出点的编号,如果遇到环,则输出-1

输入
第一行2个整数n和m
第二行开始连续m行,每行2个整数x和y,表示x这个点有一条指向y这个点的边

输出
按照拓扑排序输出每个点的编号。数字之间有1个空格,如果有多个点都是0入度,则按照数字顺序输出。

样例输入
样例输入一
3 2
1 2
2 3
样例输入二
3 3
1 2
2 3
3 2

样例输出
样例输出一
1 2 3
样例输出二
-1
搜索更多相关主题的帖子: 拓补 拓扑 排序 输出 输入 
2019-12-01 14:08
雪影辰风
Rank: 6Rank: 6
来 自:衡阳市
等 级:贵宾
威 望:22
帖 子:177
专家分:387
注 册:2019-6-17
收藏
得分:0 
温馨提示:作为一名合格的OI队员,要做到独立思考哦!

这道题其实就是一个模拟题(虽然我模拟得很烂),大概是根据作者思路而来的,所以实在没做出也没事,多去理解一下题目的意思,然后再暴力程序上优化
【因为我只测试了几个数据,发现都符合题意,若代码有问题可以回复我,我会尽力改的,谢谢!】
程序代码:
#include<cstdio>
using namespace std;
struct node {
    int x,y;
};
int n,m;
node g[1001];
bool t[1001];
int main() {
    scanf("%d %d",&n,&m);
    for(int i=1; i<=m; i++) {
        scanf("%d %d",&g[i].x,&g[i].y);
        if(t[g[i].y]) {
            printf("-1");
            return 0;
        }
        t[g[i].x]=true;
        t[g[i].y]=true;
    }
    bool first=false;
    for(int i=1; i<=1000; i++) {
        if(t[i]&&first) {
            printf(" %d",i);
            continue;
        }
        if(t[i]) {
            printf("%d",i);
            first=true;
        }
    }
    return 0;
}
2019-12-13 22:06
快速回复:拓补排序
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019992 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved