首页 > 其他分享 >拓补排序

拓补排序

时间:2023-08-06 16:56:51浏览次数:31  
标签:cnt 排序 int pd include 拓补

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack> 
#define N 1001
using namespace std;
int n,m,x,y;//顶点,边, 
vector<int> G[N];//动态数组 
stack<int> q;
int cnt[N],tpc;
bool pd(){
    for(int i=1;i<=n;i++){
        if(cnt[i]==0){
            q.push(i);//入栈 
        }
        while(!q.empty()){
            int u=q.top();//栈顶 
            q.pop();//出顶 
            tpc++;//统计出栈个数 
            cout<<u<<" ";
            for(int i=0;i<G[u].size();i++){
                int v=G[u][i];
                cnt[v]--;
                if(!cnt[v]){
                    q.push(v);
                }
            }
            if(tpc!=n)return 1;
            else return 0;
        }
    }
} 
int main(){
    cin>>n>>m;
    while(m--){
        cin>>x>>y;
        G[x].push_back(y);
        cnt[y]++;
    }
    if(pd())cout<<"存在有向环";
    else cout<<"不存在有向环"; 
    return 0;
}

 

标签:cnt,排序,int,pd,include,拓补
From: https://www.cnblogs.com/AndyYuan/p/17609556.html

相关文章

  • 输入任意整数,直到输入-1,用插入法排序以5行形式打印输出
    intmain(){ inta[100]; inti=0;intj=0;intn=0;intk=0; scanf("%d",&a[n]); n=0; while(a[n]!=-1) { n++; scanf("%d",&a[n]); } printf("BeforeSort:\n"); for(i=0;i<n;i++) { printf("%d",a[i......
  • C/C++ 数据结构-直接选择排序
    #include<iostream>#include<Windows.h>usingnamespacestd;voidswap(int*num1,int*num2){inttemp=*num1;*num1=*num2;*num2=temp;}intmain(){intret[]={161,156,170,164,158,180,159,185,172,176};intlen=......
  • 冒泡排序
    defbubble_sort(nums):  n=len(nums)  foriinrange(n-1):    forjinrange(n-i-1):      ifnums[j]>nums[j+1]:        nums[j],nums[j+1]=nums[j+1],nums[j]nums=[5,3,8,2,1]print("排序前:",nums)bubble_sort(......
  • 基数排序详解
    基数排序详解1)前言:计数排序要学基数排序,掌握计数排序非常重要。计数排序的原理十分的简单。举个例子,排序52413,你打算怎么办?很简单是不是,冒泡排序、选择排序、归并排序……这些都足以解决。但如果你有100000000个数要排序,你可能就要束手就擒了。那如归这时候我告诉你:这1000......
  • c#学习笔记----------------c#简单算法之排序算法
     排序算法参考文章:https://blog.csdn.net/weixin_61361738/article/details/128794945冒泡排序namespaceConsoleApp1{internalclassProgram{staticvoidMain(string[]args){stringstr=Console.ReadLine();str......
  • SQL分页优化三 降序排序+分页
    测试验证如下SQL:select*from(select*from(selecta.*,rownumrnfrom(select*fromtestorderbyobject_id,object_namedesc)a)whererownum<=10)wherern>......
  • 考研数据结构——每日一题[二叉排序树]
    3786.二叉排序树你需要写一种数据结构,来维护一些数,其中需要提供以下操作:插入数值x。删除数值x。输出数值x的前驱(前驱定义为现有所有数中小于x的最大的数)。输出数值x的后继(后继定义为现有所有数中大于x的最小的数)。题目保证:操作1插入的数值各不相同。操作......
  • MySQL查询排序和分页
    连接数据库mysql-hlocalhost-uroot-proot排序查询语法:select字段列表from表名orderby字段1排序方式1,字段3排序方式2,字段3排序方式3,....;ASC:升序(默认值)DESC降序注意:如果是多字段排序,当第一个字段值相同时,才会根据第二个字段进行排序。根据年龄对公司......
  • 5445.子数组和排序后的区间和
          1intcmp(constvoid*a,constvoid*b)2{3return*(int*)a-*(int*)b;4}5intrangeSum(int*nums,intnumsSize,intn,intleft,intright){6if(n<=0)returnNULL;7intm=numsSize*(numsSize+1)/2,i,j,k;8intn......
  • 排序
    排序知识框架No.1排序的基本概念一、排序定义排序,就是重新排列表中的元素,使表中的元素满足按关键字有序的过程。为了查找方便,通常希望计算机中的表是按关键字有序的。排序的确切定义如下:输入:n个记录R1,R2,...,Rn,对应的关键字为k1,k2,...,kn。输出:......