专栏首页ACM算法日常CodeForces 982F:The Meeting Place Cannot Be Changed(有向图)

CodeForces 982F:The Meeting Place Cannot Be Changed(有向图)

题目:

Petr is a detective in Braginsk. Somebody stole a huge amount of money from a bank and Petr is to catch him. Somebody told Petr that some luxurious car moves along the roads without stopping.

Petr是Braginsk镇的一名侦探,现在有个人偷了很多钱,Petr需要抓捕他。有人告诉Petr有一些豪华车在路上违法行驶。

Petr knows that it is the robbers who drive the car. The roads in Braginsk are one-directional and each of them connects two intersections. Petr wants to select one intersection such that if the robbers continue to drive the roads indefinitely, they will sooner or later come to that intersection. The initial position of the robbers is unknown. Find such an intersection that fits the requirements.

Petr知道这是那些小偷在开车。Braginsk镇的路是单向的,并且每一条路有2个交点,Petr想选一个交点,如果小偷一直开车,他迟早会来到那个交点。小偷初始位置并不清楚,让你帮忙寻找这个交点。

Input

The first line of the input contains two integers n and m (2≤n≤10^5,2≤m≤5⋅10^5) — the number of intersections and the number of directed roads in Braginsk, respectively.

Each of the next mm lines contains two integers uiui and vivi (1≤ui,vi≤n,ui≠vi) —

the start and finish of the i-th directed road. It is guaranteed that the robbers can move along the roads indefinitely.

Output

Print a single integer kk — the intersection Petr needs to choose. If there are multiple answers, print any. If there are no such intersections, print −1−1.

Examples

input

Copy

5 6

1 2

2 3

3 1

3 4

4 5

5 3

output

Copy

3

input

Copy

3 3

1 2

2 3

3 1

output

Copy

1

Note

In the first example the robbers can move, for example, along the following routes: (1−2−3−1)(1−2−3−1), (3−4−5−3)(3−4−5−3), (1−2−3−4−5−3−1)(1−2−3−4−5−3−1). We can show that if Petr chooses the 33-rd intersection, he will eventually meet the robbers independently of their route.

题意: 劫匪的初始位置未知,他沿着道路不停的移动, 城市的道路是单向的,并且每条道路都连接两个交叉路口, 选择一个交叉路口,如果劫匪继续无限期地开车, 他们迟早会到达那个交叉路口。 分析:

考察有向图的存储、遍历、判断有环 先按入度从大到小给每个点排序,然后枚举每个点当作答案,判断当前点是否行


#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 50; //数据量
int n, m; //节点数、边数
int head[N], to[N], nxt[N], tot; //存储有向图
inline void add(int x, int y) //x为起点,y为终点建边
{
    to[tot] = y;
    nxt[tot] = head[x];
    head[x] = tot++;
}
int vis[N];//标记已经访问过的节点
int in[N], id[N];
bool dt[N], k;
const bool cmp(int a, int b) //间接排序函数
{
    return in[a] < in[b]; //按入度排序
}
//计算搜索时间
inline double FIND_TIME()
{return clock() / (double)CLOCKS_PER_SEC;}
void dfs(int x)
{
    vis[x] = 1; //标记节点已经访问过
    for (int i = head[x]; ~i; i = nxt[i])
    {
        if (!vis[to[i]]) //下一个节点没有访问过
            dfs(to[i]);
        if (vis[to[i]] == 1) //下一个节点访问过
            k = 1;
        if (k)   return ;
    }
    vis[x] = 2; //DFS回溯
}
inline bool check(int x)//检查每一个点
{
    memset(vis, 0, sizeof(vis));
    vis[x] = 2;
    k = 0;
    for (int i = 1; i <= n; i++)
        if (!vis[i]) {
            dfs(i);
            if (k) {
                for (int i = 1; i <= n; i++)
                    if (vis[i] != 1)
                        dt[i] = 1;
                return false;
            }
        }
    return true;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v); //建边
        ++in[u];//更新度
    }
    for (int i = 1; i <= n; i++)
        id[i] = i; //节点编号
    sort(id + 1, id + 1 + n, cmp); //排序
    for (int i = 1; i <= n; i++) {
        if (FIND_TIME() > 0.9) break; //时间限制为1s
        if (!dt[id[i]] && check(id[i])) //此点合法
        {
            printf("%d\n", id[i]); //输出路口的编号
            return 0;
        }
    }
    puts("-1");//不存在这样的点
    return 0;
}

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:紫芝眉宇

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Planning mobile robot on Tree (EASY Version)(UVA12569,状态压缩)

    题目链接:https://vjudge.net/problem/UVA-12569

    ACM算法日常
  • 搜索专题2 | 3D地宫寻路 POJ - 2251

    上一篇我们做了一道棋子摆放的题目,采用的是DFS算法,本篇是一篇BFS算法,在刚开始学习搜索算法的时候,会觉得DFS和BFS算法非常相似,因为都是搜索然后得到结...

    ACM算法日常
  • 翻转瓷砖Fliptile(开关反转)- POJ 3279

    Farmer John knows that an intellectually satisfied cow is a happy cow who will g...

    ACM算法日常
  • ZOJ 3326 An Awful Problem(模拟)

    An Awful Problem ---- Time Limit: 1 Second      Memory Limit: 32768 KB ---- In o...

    ShenduCC
  • 实验2 C++数组与指针

    步行者08
  • Codeforce-Ozon Tech Challenge 2020-D. Kuroni and the Celebration(交互题+DFS)

    After getting AC after 13 Time Limit Exceeded verdicts on a geometry problem, Ku...

    风骨散人Chiam
  • 图论--差分约束--POJ 3159 Candies

    风骨散人Chiam
  • CF--思维练习--CodeForces - 216C - Hiring Staff (思维+模拟)

    ACM思维题训练集合 A new Berland businessman Vitaly is going to open a household applia...

    风骨散人Chiam
  • Java字节码修改库ASM#ClassReader实现原理及源码分析

    ASM是Java中比较流行的用来读写字节码的类库,用来基于字节码层面对代码进行分析和转换。

    JavaEdge
  • CF--思维练习--CodeForces - 221C-H - Little Elephant and Problem (思维)

    ACM思维题训练集合 The Little Elephant has got a problem — somebody has been touching h...

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券