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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Coding01

浅谈 Laravel Collections

这两天看了两本书《Laravel Collections Unraveled》和 《Refactoring to Collections》。

3412
来自专栏专知

【 关关的刷题日记50】 Leetcode 345. Reverse Vowels of a String

关关的刷题日记50 – Leetcode 345. Reverse Vowels of a String 题目 Write a function that ta...

2673
来自专栏平凡文摘

国外大神总结的 10 个 Java 编程技巧!

1232
来自专栏java一日一条

为什么要使用String

这段代码总的来说是OK的。该方法将map中每个Dwarable的key和值,以及和它期望被分解的dwarwleKey一同传得给另一个调用方法。因为功能简单,我就...

742
来自专栏精讲JAVA

面向对象VS面向过程

1 前言 向伟人致敬 其实这个问题真的是被问烂了,特别是刚入门的同行,我感觉这个问题应该是大家都听说过了,但是有多少人真的是理解这两个区别呢,这两...

2065
来自专栏java一日一条

由字符串反转(使用递归)引申出来一道Java面试题

在Java中,最好的实现就是用JDK中StringBuffer的反转方法,它不仅速度快,效率高,而且还知道如何处理unicode代理对(surrogate p...

791
来自专栏tkokof 的技术,小趣及杂念

Sweet Snippet 之 Bounce Setting

  又是一篇Sweet Snippet,自己看来都觉得过小,不足以成篇,不过自觉有些趣味,也就随便记一记了,权当自娱自乐 :)

581
来自专栏java一日一条

由字符串反转(使用递归)引申出来一道Java面试题

如何面试一个从事编程工作的开发人员既困难又乏味,幸好还有很多值得参考的指南,比如:《Joel Guerilla Guide to interviewing》,...

882
来自专栏一个会写诗的程序员的博客

用 Kotlin 的函数式编程 替代 GOF 设计模式用 Kotlin 的函数式编程 替代 GOF 设计模式函数式编程(FP)《Kotlin极简教程》正式上架:

"函数式编程", 又称泛函编程, 是一种"编程范式"(programming paradigm),也就是如何编写程序的方法论。它的基础是 λ 演算(lambda...

1404
来自专栏一个会写诗的程序员的博客

编程范式 (Programming paradigm)

范,模范、典范也。范式即模式、方法。常见的编程范式有:函数式编程、程序编程、面向对象编程、指令式编程等。

3301

扫码关注云+社区

领取腾讯云代金券