洛谷P2296 [NOIP2014 提高组] 寻找道路 题解

题目链接：P2296 [NOIP2014 提高组] 寻找道路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

好了，话不多说上代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct node
 4 {
 5     int to,next;
 6 }q[200005];
 7 struct edge
 8 {
 9     int x,y;
10 }e[200005];
11 int n,m,h[200005],cnt=0,dis[200005],p[200005],s,t,vis[200005],tag[200005];
12 void qxx(int x,int y)
13 {
14     cnt++;
15     q[cnt].to=y;
16     q[cnt].next=h[x];
17     h[x]=cnt;
18 }
19 void dfs(int x)
20 {
21     vis[x]=1;
22     for(int i=h[x];i;i=q[i].next)
23     {
24         int y=q[i].to;
25         if(!vis[y]) dfs(y);
26     }
27 }
28 int main()
29 {
30     scanf("%d%d",&n,&m);
31     for(int i=1;i<=m;i++)
32     {
33         int x,y;
34         scanf("%d%d",&x,&y);
35         e[i].x=x;
36         e[i].y=y;
37         if(x==y) continue;
38         qxx(y,x);
39     }
40     scanf("%d%d",&s,&t);
41     dfs(t);
42     memset(h,0,sizeof(h));
43     cnt=0;
44     for(int i=1;i<=m;i++)
45     {
46         if(e[i].x!=e[i].y) qxx(e[i].x,e[i].y);
47     }
48     for(int x=1;x<=n;x++)
49     {
50         tag[x]=1;
51         for(int i=h[x];i;i=q[i].next)
52         {
53             int y=q[i].to;
54             if(!vis[y])
55             {
56                 tag[x]=0;
57                 break;
58             }
59         }
60     }
61     memset(dis,-1,sizeof(dis));
62     if(!tag[s])
63     {
64         printf("-1");
65         return 0;
66     }
67     int l=0,r=1;
68     p[1]=s;
69     dis[s]=0;
70     while(l<r)
71     {
72         int x=p[++l];
73         for(int i=h[x];i;i=q[i].next)
74         {
75             int y=q[i].to;
76             if(!tag[y]) continue;
77             if(dis[y]==-1)
78             {
79                 dis[y]=dis[x]+1;
80                 p[++r]=y;
81             }
82         }
83     }
84     printf("%d",dis[t]);
85     return 0;
86 }