头像

JasonQ1an




离线:48分钟前


最近来访(430)
用户头像
秘封の月列
用户头像
Hfour9
用户头像
微笑_8
用户头像
从前
用户头像
南骁.
用户头像
-浪漫主义狗-
用户头像
navystar
用户头像
boring
用户头像
霹雳暴龙战士
用户头像
小土豆1123
用户头像
ShyWind
用户头像
ZagY
用户头像
绯色月下
用户头像
Process531
用户头像
notion
用户头像
凌乱之风
用户头像
249156850
用户头像
心有远方从未止步
用户头像
迷人的源
用户头像
学的开心

活动打卡代码 AcWing 3786. 二叉排序树

JasonQ1an
18天前

你需要写一种数据结构,来维护一些数,其中需要提供以下操作:

  1. 插入数值 $x$。
  2. 删除数值 $x$。

题目保证:

  • 操作 $1$ 插入的数值各不相同。
  • 操作 $2$ 删除的数值一定存在。

输入格式

第一行包含整数 $n$,表示共有 $n$ 个操作命令。

接下来 $n$ 行,每行包含两个整数 $opt$ 和 $x$,表示操作序号和操作数值。

输出格式

对于操作 $3,4$,每行输出一个操作结果。

数据范围

$1 \le n \le 2000$,
$-10000 \le x \le 10000$

输入样例:

6
1 1
1 3
1 5
3 4
2 3
4 2

输出样例:

3
5

思路

插入操作

image-20221108170605414

删除操作

对于一个二叉排序树来说,中序遍历(左中右)是有序的。

有三种情况

  1. 该节点为叶节点
  2. 该节点存在一个左节点,或者一个右节点
  3. 该节点存在左节点、右节点

重点说明一下第三种情况:由于是一颗二叉排序树,故节点$X$的左子树中最右的根节点$A$一定是左子树中最大的值,故将节点$A$的值赋值给节点$X$,再递归遍历左子树,删除节点$A$。

image-20221108170636844

Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;
    TreeNode(int _val): val(_val), left(NULL), right(NULL) {}
};

int n;

// 如果不用引用传入,那么root 就是一个形参,此函数由于要修改root,故传入引用
void insert(TreeNode* &root, int x)  
{
    if(root == NULL) root = new TreeNode(x);  // 如果为空,则插入该节点
    else if(root->val > x) insert(root->left, x);  // 如果该节点的值大于x,则递归插入左边
    else insert(root->right, x);  // 如果该节点的值大于x,则递归插入右边
}

void remove(TreeNode* &root, int x)
{
    if(root == NULL) return;  // 表示没有x这个元素

    if(root->val > x) remove(root->left, x);  // 如果该节点的值大于x,则递归查找左边
    else if(root->val < x) remove(root->right, x);  // 如果该节点的值大于x,则递归查找右边
    else  // 就是该点
    {
        if(root->left == NULL && root->right == NULL) root = NULL;  // 该点为叶节点,直接删
        else if(root->left == NULL) root = root->right;  // 如果左边为空,则将右节点提上来
        else if(root->right == NULL) root = root->left;  // 如果右边为空,则将左节点提上来
        else  // 左右节点都不为空
        {
            auto p = root->left;  // 定义一个探寻左子树中最大值的节点
            while(p->right != NULL) p = p->right;  // 由于二叉排序树的定义,左子树的右儿子一定是最大值
            swap(root->val, p->val);  // 交换两个的值
            remove(root->left, p->val);  // 递归处理左子树,删除节点p这个节点
        }
    }
}

int main()
{
    TreeNode* root;
    cin >> n;
    while(n -- )
    {
        int opt, x;
        cin >> opt >> x;
        if(opt == 1) insert(root, x);
        else if(opt == 2) remove(root, x);
    }

    return 0;
}



JasonQ1an
21天前

840.模拟散列表

维护一个集合,支持如下几种操作:

  1. I x,插入一个数 $x$;
  2. Q x,询问数 $x$ 是否在集合中出现过;

现在要进行 $N$ 次操作,对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 $N$,表示操作数量。

接下来 $N$ 行,每行包含一个操作指令,操作指令为 I xQ x 中的一种。

输出格式

对于每个询问指令 Q x,输出一个询问结果,如果 $x$ 在集合中出现过,则输出 Yes,否则输出 No

每个结果占一行。

数据范围

$1 \le N \le 10^5$
$-10^9 \le x \le 10^9$

输入样例:

5
I 1
I 2
I 3
Q 2
Q 5

输出样例:

Yes
No

开散列方法(拉链法)

核心:如果一个位置有多个重复映射到此处的元素,就开一个链表,将所有元素都存储下来。

$Code$:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200003;  // ①空间大小为质数,②空间开数据的两倍,使得负载因子为1/2

int h[N], e[N], ne[N], idx;
int n;

bool find(int x)  // 查询x是否在哈希表中
{
    int t = (x % N + N) % N;  // 此处通过除余法计算哈希函数
    // 加N再模N是为了避免在c++中模运算为负的情况

    for(int i = h[t]; i != -1; i = ne[i])
        if(e[i] == x) return true;

    return false;
}

void add(int a, int b)  // 在链表a中插入b这个元素(注意区别于a->b连接一条边,代码相同,含义不同)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void insert(int x)
{
    // 在哈希计算后,判断是否存在当前元素
    if(find(x)) return;  // 如果找到了就不进行插入操作


    // 没有找到,进行插入操作,在位置为t的链表中插入x这个元素

    int t = (x % N + N) % N;  // 此处通过除余法计算哈希函数
    // 加N再模N是为了避免在c++中模运算为负的情况

    add(t, x);
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h);  // 初始化邻接表的表头

    while(n -- )
    {
        char op[2];  // 使用字符串来读取字符可以有效地避免空格造成的输入影响
        int x;
        scanf("%s%d", op, &x);
        if(op[0] == 'I') insert(x);
        else 
        {
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

闭散列方法(开放寻址法)

核心:如果映射到某个位置$A$的时候,此位置$A$已经存在元素,则映射到它下一个位置$B$,如果下一个位置$B$还是存在元素,则映射到$B$的下一个的位置。(ps:如果映射到最后一个位置$N-1$,并且该位置已经存在元素,则映射到开头的位置$0$)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;
// ①空间大小为质数,②空间开数据的两倍,使得负载因子为1/2
// null: 当前位置是否存在元素,作为判断依据

int n;
int h[N];  // 定义哈希表的长度

int find(int x)  // 查询哈希函数后的位置
{
    int t = (x % N + N) % N;  // 此处通过除余法计算哈希函数
    // 加N再模N是为了避免在c++中模运算为负的情况

    while(h[t] != null && h[t] != x)  // 如果当前位置不为空 并且 当前位置上元素与查询的元素不相同
        t = (t + 1) % N;  // 往后移动一位,当移动到最后一个元素,则从开头移动

    return t;  // 返回哈希处理后的位置
}

int main()
{
    scanf("%d", &n);

    memset(h, 0x3f, sizeof h);  // 将哈希表所有位置定义为不存在元素的状态

    while(n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);

        if(op[0] == 'I') h[find(x)] = x;
        else 
        {
            if(h[find(x)] != x) puts("No");
            else puts("Yes");
        }
    }

    return 0;
}



JasonQ1an
22天前
class Solution {
public:
    int findMissMin(vector<int>& nums) {
        int n = nums.size();
        vector<bool> hash(n + 1);
        for(auto i : nums)
            if(i >= 1 && i <= n)
                hash[i] = true;
        for(int i = 1; i <= n; i ++ )
            if(!hash[i])
                return i;
        return n + 1;
    }
};


活动打卡代码 AcWing 840. 模拟散列表

JasonQ1an
22天前

840.模拟散列表

维护一个集合,支持如下几种操作:

  1. I x,插入一个数 $x$;
  2. Q x,询问数 $x$ 是否在集合中出现过;

现在要进行 $N$ 次操作,对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 $N$,表示操作数量。

接下来 $N$ 行,每行包含一个操作指令,操作指令为 I xQ x 中的一种。

输出格式

对于每个询问指令 Q x,输出一个询问结果,如果 $x$ 在集合中出现过,则输出 Yes,否则输出 No

每个结果占一行。

数据范围

$1 \le N \le 10^5$
$-10^9 \le x \le 10^9$

输入样例:

5
I 1
I 2
I 3
Q 2
Q 5

输出样例:

Yes
No

开散列方法(拉链法)

核心:如果一个位置有多个重复映射到此处的元素,就开一个链表,将所有元素都存储下来。

$Code$:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200003;  // ①空间大小为质数,②空间开数据的两倍,使得负载因子为1/2

int h[N], e[N], ne[N], idx;
int n;

bool find(int x)  // 查询x是否在哈希表中
{
    int t = (x % N + N) % N;  // 此处通过除余法计算哈希函数
    // 加N再模N是为了避免在c++中模运算为负的情况

    for(int i = h[t]; i != -1; i = ne[i])
        if(e[i] == x) return true;

    return false;
}

void add(int a, int b)  // 在链表a中插入b这个元素(注意区别于a->b连接一条边,代码相同,含义不同)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void insert(int x)
{
    // 在哈希计算后,判断是否存在当前元素
    if(find(x)) return;  // 如果找到了就不进行插入操作


    // 没有找到,进行插入操作,在位置为t的链表中插入x这个元素

    int t = (x % N + N) % N;  // 此处通过除余法计算哈希函数
    // 加N再模N是为了避免在c++中模运算为负的情况

    add(t, x);
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h);  // 初始化邻接表的表头

    while(n -- )
    {
        char op[2];  // 使用字符串来读取字符可以有效地避免空格造成的输入影响
        int x;
        scanf("%s%d", op, &x);
        if(op[0] == 'I') insert(x);
        else 
        {
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

闭散列方法(开放寻址法)

核心:如果映射到某个位置$A$的时候,此位置$A$已经存在元素,则映射到它下一个位置$B$,如果下一个位置$B$还是存在元素,则映射到$B$的下一个的位置。(ps:如果映射到最后一个位置$N-1$,并且该位置已经存在元素,则映射到开头的位置$0$)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;
// ①空间大小为质数,②空间开数据的两倍,使得负载因子为1/2
// null: 当前位置是否存在元素,作为判断依据

int n;
int h[N];  // 定义哈希表的长度

int find(int x)  // 查询哈希函数后的位置
{
    int t = (x % N + N) % N;  // 此处通过除余法计算哈希函数
    // 加N再模N是为了避免在c++中模运算为负的情况

    while(h[t] != null && h[t] != x)  // 如果当前位置不为空 并且 当前位置上元素与查询的元素不相同
        t = (t + 1) % N;  // 往后移动一位,当移动到最后一个元素,则从开头移动

    return t;  // 返回哈希处理后的位置
}

int main()
{
    scanf("%d", &n);

    memset(h, 0x3f, sizeof h);  // 将哈希表所有位置定义为不存在元素的状态

    while(n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);

        if(op[0] == 'I') h[find(x)] = x;
        else 
        {
            if(h[find(x)] != x) puts("No");
            else puts("Yes");
        }
    }

    return 0;
}



JasonQ1an
29天前

题目链接 3693. 括号匹配

出现Segmentation Fault,代码数据过了$(12/14)$。

望大佬指点指点QAQ

错误的代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <unordered_map>

using namespace std;

string str;
stack<char> op;

unordered_map<char, int> mp{{'(', 1}, {')', 1}, {'[', 2}, {']', 2}, {'{', 3}, {'}', 3}, {'<', 4}, {'>', 4}};

int main()
{
    cin >> str;
    for(int i = 0; i < str.size(); i ++ )
    {
        if(str[i] == '<' || str[i] == '[' || str[i] == '{' || str[i] == '(') op.push(str[i]);
        else
        {
            if(mp[op.top()] != mp[str[i]]) 
            {
                puts("no");
                return 0;
            }
            else 
            {
                op.pop();
            }
        }
    }

    if(op.size() == 0) puts("yes");
    else puts("no");

    return 0;
}

编译器报了什么错误:Segmentation Fault



活动打卡代码 AcWing 3302. 表达式求值

JasonQ1an
1个月前

题意

给定一个表达式,其中运算符仅包含 +,-,*,/(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。

注意:

  • 数据保证给定的表达式合法。
  • 题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
  • 题目保证表达式中所有数字均为正整数。
  • 题目保证表达式在中间计算过程以及结果中,均不超过 $2^{31}-1$。
  • 题目中的整除是指向 $0$ 取整,也就是说对于大于 $0$ 的结果向下取整,例如 $5/3=1$,对于小于 $0$ 的结果向上取整,例如 $5/(1-4) = -1$。
  • C++和Java中的整除默认是向零取整;Python中的整除//默认向下取整,因此Python的eval()函数中的整除也是向下取整,在本题中不能直接使用。

输入格式

共一行,为给定表达式。

输出格式

共一行,为表达式的结果。

数据范围

表达式的长度不超过 $10^5$。

输入样例:

(2+2)*(1+1)

输出样例:

8

思想

表达式求值:

  1. 如果当前元素是数字:压入
  2. 如果当前元素是(:压入
  3. 如果当前元素是):操作到(
  4. 如果当前元素是+-*/:操作到(或者栈顶优先级$<$当前元素的优先级

操作完运算符栈后,数栈栈顶为答案。

Code

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <unordered_map>

using namespace std;

unordered_map<char, int> h{{'+','1'}, {'-','1'}, {'*','2'}, {'/','2'}};  // 定义操作符的优先级。

stack<char> op;  // 定义运算符栈
stack<int> nums; // 定义数栈

void eval()
{
    // 这里要注意栈存储是先进先出,
    // 因此运算时要用第二个数栈的值处理第一个数栈的值(主要体现在除法的差异)
    int b = nums.top();
    nums.pop();

    int a = nums.top();
    nums.pop();

    char c = op.top();
    op.pop();

    int x;
    if(c == '+') x = a + b;
    if(c == '-') x = a - b;
    if(c == '*') x = a * b;
    if(c == '/') x = a / b;

    // 操作完毕后
    nums.push(x);  // 数入栈
}

int main()
{
    string str;
    cin >> str;

    for(int i = 0; i < str.size(); i ++ )
    {
        // 第一种情况
        // isdigit() 函数用来判断一个字符是否是数字,也即 0~9, 头文件为<iostream>
        if(isdigit(str[i]))  
        {
            // 将数字抠出来
            int j = i, sum = 0;
            while(j < str.size() && isdigit(str[j]))
            {
                sum = sum * 10 + str[j] - '0';
                j ++ ;
            }
            // 将数字加入数栈
            nums.push(sum);

            i = j - 1;  // 因为for循环结束后,i ++ 
        }
        else if(str[i] == '(') op.push(str[i]);  // 第二种情况
        else if(str[i] == ')')  // 第三种情况
        {
            while(op.top() != '(')
            {
                eval();
            }
            op.pop();  // 此处弹出的就是')'
        }
        else  // 第四种情况 
        {
            while(op.size() && h[op.top()] >= h[str[i]])
            {
                eval();
            }
            op.push(str[i]);
        }
    }

    while(op.size()) eval();  // 如果所有括号都处理完毕,处理剩下的运算符

    cout << nums.top() << endl;

    return 0;
}


活动打卡代码 AcWing 854. Floyd求最短路

JasonQ1an
1个月前
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 310, INF = 0x3f3f3f3f;

int n, m, q;
int d[N][N];

void floyd()
{
    for(int k = 1; k <= n; k ++ )
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
    cin >> n >> m >> q;

    memset(d, 0x3f, sizeof d);

    for(int i = 1; i <= n; i ++ ) d[i][i] = 0;

    while(m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }

    floyd();

    while(q -- )
    {
        int a, b;
        cin >> a >> b;
        int t = d[a][b];
        if(t > INF / 2) puts("impossible");
        else cout << t << endl;
    }

    return 0;
}



JasonQ1an
1个月前

参考文献: 最短路笔记
最短路.png

最短路中各个算法的原理

①dijkstra

时间复杂度$O(n^2)$
dijkstra是根据每次找出距离起点最近的一个点,然后用着一个点来更新其他距离,每个点只会被更新一次,用st[]进行判重

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

②dijkstra堆优化

时间复杂度$O(mlogn)$
堆优化的dijkstra就是用c++自带的priority_queue优先队列对每个点i以及起点到i的距离dist进行储存,并按照距离dist进行排序

priority_queue定义: priority_queue<PII, vector<PII>, greater<PII>> heap;

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

③bellman_ford

时间复杂度$O(nm)$

通过循环点的个数n,边的个数m,来更新所有点到起点的距离
两重循环 for n
            for 所有边 a, b, w
                dist[b] = min(dist[b], dist[a] + w)

bellman_ford可以用于求有边数限制的最短路
AcWing 853.有边数限制的最短路

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

④spfa

时间复杂度平均$O(km)$线性,最坏情况下$O(nm)$

spfa就是对bellman_ford做了一个优化
因为dist[b] = min(dist[b], dist[a] + w)
a -> b
如果dist[b]要变小,那么只有dist[a]变小了才会变小。
那么做法就是:
1.维护一个队列,先把起点放进去。
2.遍历队列,每次出队的时候标记当前的点是已经被遍历过的
3.用当前的点更新其他点的距离,更新完毕后,判断当点的是否被标记过,如果没有标记过,将这个的点放入队列中,因为此时当前点一定是距离起点最小的点,满足spfa优化条件
4.遍历完所有点后判断dist[end] > INF?  因为spfa可以用来求负权边的最短路

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

⑤floyd

时间复杂度$O(n^3)$

for(int k = 1; k <= n; k ++ )   //  将其分为[i, k]和[k, j]两段,基于动态规划
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

$\color{#FF7F50}{}$
$\color{#FF4500}{}$

注意事项

稀疏图和稠密图

                 稠密图          稀疏图
边与点的个数      m≈n²           m≈n
存储方式         邻接表          邻接矩阵 

朴素版dijkstra:$Code$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010, INF = 0x3f3f3f3f;

int n, m;
int g[N][N], dist[N];
bool st[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for(int i = 0; i < n; i ++ )
    {
        int t = -1;
        for(int j = 1; j <= n; j ++ )
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = true;

        for(int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(g, 0x3f, sizeof g);

    while(m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }

    int res = dijkstra();
    if(res == INF) puts("-1");
    else printf("%d\n", res);

    return 0;
}



JasonQ1an
1个月前

朴素版prim算法 O(n^2)


prim算法的思想就是:先使得一个顶点在一个集合中,然后从这个顶点出发更新其他点到集合中的最小距离,再从集合中选取一个到集合中最短且没有使用过的顶点来更新其他点到集合中的距离。时间复杂度由于有$n$个点,每个点要更新$n$次,所以是$O(n^2)$的复杂度

$Code$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N], dist[N];  // g[i][j]:i和j之间的路径长度;dist[i]:i到集合的距离
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    dist[1] = 0;
    for(int i = 0; i < n; i ++ )
    {
        int t = -1;
        for(int j = 1; j <= n; j ++ )
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if(dist[t] == INF) return INF;
        st[t] = true;
        res += dist[t];

        for(int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], g[t][j]);  // 更新j到集合的距离,因为t已经在集合中,
                                              // 只需要比较j到集合中的距离与j到t的距离取最小值。
    }

    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);
    while(m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int ans = prim();
    if(ans == INF) puts("impossible");
    else printf("%d\n", ans);

    return 0;
}

kruskal

kruskal算法思想:将所有边按照边权按照从小到大排序,然后遍历所有的边,如果当前边的两个点不在同一个集合中,就将它们加入同一个集合中(使用并查集),最后判断加入的边是否为$n$,进行判断是否为连通图。

$Code$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010;

int n, m;
int p[N];
struct Edge
{
    int a, b, c;
    bool operator< (const Edge &t) const 
    {
        return c < t.c;
    }
}e[M];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        e[i] = {a, b, c};
    }

    sort(e, e + m);

    for(int i = 1; i <= n; i ++ ) p[i] = i;  // 初始化并查集。

    int cnt = n;
    int res = 0;
    for(int i = 0; i < m; i ++ )
    {
        int a = find(e[i].a), b = find(e[i].b);
        if(a != b) 
        {
            p[a] = b;
            cnt -- ;
            res += e[i].c;
        }
    }

    if(cnt > 1) puts("impossible");
    else printf("%d\n", res);

    return 0;
}



JasonQ1an
1个月前
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Node 
{
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL) {}
}*head[N];

int d[N], q[N];  // d:统计每个点的入度数,q数组模拟队列
// q队列中的元素就是拓扑排序的结果
int n, m, top;

void add(int a, int b)  // a到b连一条边
{
    // 如何理解?看图
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

bool topsort()
{
    int hh = 0, tt = -1;

    // 将度数为0的点入队
    for(int i = 1; i <= n; i ++ )
        if(d[i] == 0)
            q[ ++ tt] = i;

    while(hh <= tt)
    {
        int t = q[hh ++ ];  // 取出对头

        // 遍历
        for(auto p = head[t]; p != NULL; p = p->next)
        {
            d[p->id] -- ;  // 减少它的一个入队数
            // 如果判断减少后入队数为0就将它加入队列中
            if(d[p->id] == 0) q[ ++ tt] = p->id;
        }
    }

    return tt == n - 1;
}

int main()
{
    cin >> n >> m;

    while(m -- )
    {
        int a, b;
        cin >> a >> b;
        d[b] ++ ;  // 入队数加一
        add(a, b);
    }

    // 有可能存在没有拓扑排序的情况,也就是出现环的时候
    // 这个时候只需要判断每个点是否入队即可,因为只有入度为0的点才会被加入队列中
    if(!topsort()) cout << "-1" << endl;
    else
    {
        for(int i = 0; i < n; i ++ )
            cout << q[i] << " ";
        cout << endl;
    }

    return 0;
}