點(diǎn)擊打開鏈接

F. The Meeting Place Cannot Be Changed

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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 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.

Input

The first line of the input contains two integers?nn?and?mm?(2≤n≤1052≤n≤105,?2≤m≤5?1052≤m≤5?105)?— 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≤n1≤ui,vi≤n,?ui≠viui≠vi)?— the start and finish of the?ii-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.

題意：
劫匪的初始位置未知，他沿著道路不停的移動(dòng)，城市的道路是單向的，并且每條道路都連接兩個(gè)交叉路口，
選擇一個(gè)交叉路口，如果劫匪繼續(xù)無限期地開車，他們遲早會(huì)到達(dá)那個(gè)交叉路口。

分析：

其實(shí)這個(gè)問題可以看做是一個(gè)強(qiáng)連通分量里面的所有簡單環(huán)是否存在至少一個(gè)公共點(diǎn)
那么我們假設(shè)一個(gè)點(diǎn)滿足條件就等價(jià)于從這個(gè)點(diǎn)出發(fā)，一定不會(huì)滯留在一個(gè)死循環(huán)中，
而是最后回到了出發(fā)點(diǎn).對所有路徑都滿足。如果這個(gè)點(diǎn)不滿足，那么應(yīng)該再去找哪個(gè)點(diǎn)呢？

這個(gè)點(diǎn)滯留在死循環(huán)中，那么就說明它不屬于這個(gè)死循環(huán)的環(huán)，所以接下來的那個(gè)點(diǎn)一定是這兩個(gè)環(huán)的交點(diǎn)，

因?yàn)樵擖c(diǎn)絕對滿足不會(huì)進(jìn)入這兩個(gè)環(huán)的死循環(huán)，接下來就是這樣找下去，直到遇到交點(diǎn)是已經(jīng)遇到過的，

那么說明有兩個(gè)交集點(diǎn)為0的環(huán)，則輸出-1.由于這樣找在有解的情況是最快的，

所以時(shí)間一多說明幾乎是無解的,則可以限時(shí)查詢的時(shí)間。

#include<bits/stdc++.h> using namespace std; const int N=5e5+50;//數(shù)據(jù)量 int n,m;//節(jié)點(diǎn)數(shù)、邊數(shù) int head[N],to[N],nxt[N],tot;//存儲(chǔ)有向圖 inline void add(int x,int y)//x為起點(diǎn)，y為終點(diǎn)建邊 {to[tot]=y;nxt[tot]=head[x];head[x]=tot++; } int vis[N];//標(biāo)記已經(jīng)訪問過的節(jié)點(diǎn) int in[N],id[N]; bool dt[N],k; const bool cmp(int a,int b)//間接排序函數(shù) {return in[a]<in[b];//按入度排序 } //計(jì)算搜索時(shí)間 inline double FIND_TIME() {return clock()/(double)CLOCKS_PER_SEC;} void dfs(int x) {vis[x]=1;//標(biāo)記節(jié)點(diǎn)已經(jīng)訪問過for(int i=head[x];~i;i=nxt[i]){if(!vis[to[i]])//下一個(gè)節(jié)點(diǎn)沒有訪問過dfs(to[i]);if(vis[to[i]]==1)//下一個(gè)節(jié)點(diǎn)訪問過k=1;if(k) return ;}vis[x]=2;//DFS回溯 } inline bool check(int x)//檢查每一個(gè)點(diǎn) {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;//節(jié)點(diǎn)編號sort(id+1,id+1+n,cmp);//排序for(int i=1;i<=n;i++){if(FIND_TIME()>0.9) break;//時(shí)間限制為1sif(!dt[id[i]]&&check(id[i]))//此點(diǎn)合法{printf("%d\n",id[i]);//輸出路口的編號return 0;} }puts("-1");//不存在這樣的點(diǎn)return 0; }

用鄰接表來存儲(chǔ)有向圖

#include<bits/stdc++.h> using namespace std; const int mx = 1e5 + 10; int n,m,in[mx],ty,type[mx],d,mark; vector <int> vec[mx]; int dfn[mx],id[mx],size,is,sta[mx]; int vis[mx],flag; bool vic[mx]; void tarjan(int x) {dfn[x] = id[x] = ++is;vis[x] = 1;sta[++size] = x;for(int i=0;i<vec[x].size();i++){int son = vec[x][i];if(!dfn[son]){tarjan(son);id[x] = min(id[x],id[son]);}else if(vis[son]) id[x] = min(id[x],dfn[son]);}if(dfn[x]==id[x]){ty++;if(sta[size]!=x) d++,mark = ty;while(sta[size]!=x){type[sta[size]] = ty;vis[sta[size]] = 0;size--;}type[x] = ty,size--,vis[x] = 0;} } void dfs(int x,int num) {if(flag) return ;for(int i=0;i<vec[x].size();i++){if(flag) return;int son = vec[x][i];if(vis[son]==num){if(vic[son]) flag = -1;else flag = son,vic[son] = 1;}if(vis[son]<num) vis[son] = num,dfs(son,num);}vis[x] = num + 1; } double TIME(){//獲得單位運(yùn)行時(shí)間return 1.0*clock()/CLOCKS_PER_SEC; } int check(int x,int num) {while(TIME()<0.5){vis[x] = num + 1;dfs(x,num);if(!flag) return x;if(flag==-1) return -1;x = flag,num += 2,flag = 0;}return -1; } int main() {scanf("%d%d",&n,&m);int a,b,c = 0,ans;for(int i=1;i<=m;i++){scanf("%d%d",&a,&b);vec[a].push_back(b);}for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i);if(d>1) puts("-1");else{for(int i=1;i<=n;i++)if(type[i]==mark){printf("%d\n",check(i,1));break;}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces 982F. The Meeting Place Cannot Be Changed的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。