当前位置:网站首页>BDF application - topology sequence
BDF application - topology sequence
2022-07-05 03:56:00 【jigsaw_ zyx】
Problem description
Given a n A little bit m Directed graph of strip edge , The number of points is 1 To n, There may be double edges and self rings in the graph .
Please output any topological sequence of the directed graph , If the topological sequence does not exist , The output -1.
If a sequence consisting of all the points in the graph A Satisfy : For each edge in the graph (x, y),x stay A All appear in y Before , said A Is a topological sequence of the graph .
Input format
The first line contains two integers n and m
Next m That's ok , Each line contains two integers x and y, Indicates that there is a from point x point-to-point y The directed side of (x, y).
Output format
All in one line , If there is a topological sequence , Then output any legal topological sequence .
Otherwise output -1.
Data range
1≤n,m≤105
sample input :
3 3
1 2
2 3
1 3
sample output :
1 2 3
Code
#include<bits/stdc++.h>
using namespace std;
const int N=100100;
int n,m;
int h[N],e[N],ne[N],idx=0;// Linked list record chart
int q[N],d[N];// Simulation queue 、 Record the degree of penetration
void add(int a,int b){
// Save map
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool topsort(){
// A topological sort
int hh=0,tt=-1;
for(int i=1;i<=n;i++)
if(d[i]==0)
q[++tt]=i;
while(hh<=tt){
int k=q[hh++];
for(int i=h[k];i!=-1;i=ne[i]){
int j=e[i];
d[j]--;
if(d[j]==0) q[++tt]=j;
}
}
return tt==n-1;
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int x,y;
cin>>x>>y;
add(x,y);
d[y]++;
}
if(topsort()){
for(int i=0;i<n;i++) cout<<q[i]<<" ";
puts("");
}else cout<<-1;
return 0;
}
边栏推荐
- Assembly - getting started
- DECLARE_ WAIT_ QUEUE_ HEAD、wake_ up_ Interruptible macro analysis
- 天干地支纪年法中为什么是60年一个轮回,而不是120年
- This article takes you to understand the relationship between the past and present of Bi and the digital transformation of enterprises
- [understand series after reading] 6000 words teach you to realize interface automation from 0 to 1
- 深度学习——LSTM基础
- Some enterprise interview questions of unity interview
- CTF stegano practice stegano 9
- How is the entered query SQL statement executed?
- [wp]bmzclub几道题的writeup
猜你喜欢
Basic knowledge of tuples
Some enterprise interview questions of unity interview
EasyCVR更改录像存储路径,不生成录像文件如何解决?
企业级:Spire.Office for .NET:Platinum|7.7.x
线上故障突突突?如何紧急诊断、排查与恢复
【看完就懂系列】一文6000字教你从0到1实现接口自动化
IronXL for .NET 2022.6
JWT vulnerability recurrence
【软件逆向-基础知识】分析方法、汇编指令体系结构
Web components series (VII) -- life cycle of custom components
随机推荐
Installation of postman and postman interceptor
speed or tempo in classical music
laravel8 导出Excle文件
特殊版:SpreadJS v15.1 VS SpreadJS v15.0
Clickhouse物化视图
[array]566 Reshape the matrix - simple
ABP vNext microservice architecture detailed tutorial - distributed permission framework (Part 2)
speed or tempo in classical music
Flex flexible layout
Monitoring web performance with performance
glibc strlen 实现方式分析
On the day 25K joined Tencent, I cried
[web source code code code audit method] audit skills and tools
Basic knowledge of tuples
It took two nights to get Wu Enda's machine learning course certificate from Stanford University
Official announcement! The third cloud native programming challenge is officially launched!
provide/inject
Enterprise level: spire Office for . NET:Platinum|7.7. x
Learning notes of raspberry pie 4B - IO communication (I2C)
Multimedia query