[题目链接]

http://uoj.ac/problem/19

[算法]

首先,在反向图上从终点广搜,求出每个点是否可以在答案路径中

然后在正向图中求出源点至终点的最短路,同样可以使用广搜

时间复杂度 : O(N)

[代码]

#include<bits/stdc++.h>
using namespace std;
#define MAXN 10010
#define MAXM 200010 struct edge
{
int to,nxt;
} e[MAXM << ]; int i,n,m,u,v,s,t,tot;
int head[MAXN],rhead[MAXN],deg[MAXN];
bool flag[MAXN]; namespace IO
{
template <typename T> inline void read(T &x)
{
int f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar())
{
if (c == '-') f = -f;
}
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
template <typename T> inline void write(T x)
{
if (x < )
{
putchar('-');
x = -x;
}
if (x > ) write(x / );
putchar(x % + '');
}
template <typename T> inline void writeln(T x)
{
write(x);
puts("");
}
} ;
inline void addedge(int u,int v)
{
tot++;
e[tot] = (edge){v,head[u]};
head[u] = tot;
}
inline void addredge(int u,int v)
{
tot++;
e[tot] = (edge){v,rhead[u]};
rhead[u] = tot;
}
inline void bfs1(int s)
{
int i,u,v,l,r;
static int q[MAXN],cnt[MAXN];
static bool visited[MAXN];
for (i = ; i <= n; i++) cnt[i] = ;
q[l = r = ] = s;
flag[s] = true;
while (l <= r)
{
u = q[l];
l++;
for (i = rhead[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (!visited[v])
{
visited[v] = true;
q[++r] = v;
}
cnt[v]++;
}
}
for (i = ; i <= n; i++) flag[i] = (cnt[i] == deg[i]);
}
inline int bfs2(int s)
{
int i,u,v,l,r;
static int q[MAXN],dist[MAXN];
static bool visited[MAXN];
if (!flag[s]) return -;
for (i = ; i <= n; i++) visited[i] = false;
q[l = r = ] = s;
dist[s] = ;
visited[s] = true;
while (l <= r)
{
u = q[l];
l++;
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (!visited[v] && flag[v])
{
visited[v] = true;
dist[v] = dist[u] + ;
q[++r] = v;
}
}
}
return dist[t] > ? dist[t] : -;
} int main()
{ IO :: read(n); IO :: read(m);
for (i = ; i <= m; i++)
{
IO :: read(u); IO :: read(v);
addedge(u,v);
addredge(v,u);
deg[u]++;
}
IO :: read(s); IO :: read(t);
bfs1(t);
IO :: writeln(bfs2(s)); return ; }

最新文章

  1. Summary of Critical and Exploitable iOS Vulnerabilities in 2016
  2. android setDestinationInExternalPublicDir 下载到SD卡根目录
  3. C++静态成员和静态成员函数
  4. 【转】CSRF攻击的应对之道
  5. Backbone之旅——Model篇
  6. 如何使用Promise
  7. Leetcode:Repeated DNA Sequences详细题解
  8. CentOS搭建PHP服务器环境(LAMP)
  9. ASP.NET Zero--12.一个例子(5)商品分类管理-编辑分类
  10. bootstrap模态框总结
  11. Number()和new Number()的区别以及一种简单实现
  12. [c++项目]迷宫 控制台游戏
  13. UnicodeDecodeError: &#39;ascii&#39; codec can&#39;t decode byte
  14. 查看oracle 用户执行的sql语句历史记录
  15. java设计模式学习
  16. Windows查看端口被什么进程占用的简单方法----菜鸟养成
  17. 多进程vs多线程
  18. Java 常见面试题(一)
  19. oralce表空间使用情况查询
  20. 从底层谈WebGIS 原理设计与实现(五):WebGIS中通过行列号来换算出多种瓦片的URL 之在线地图

热门文章

  1. ajax不跳转页面的快速删除操作,可添加美观样式
  2. Storm 入门一:基本知识+网上资源链接
  3. JS高级——封装注册事件
  4. How an SSL connection is established
  5. iOS UIWebView 访问https绕过证书验证的方法
  6. TCP:三次握手,URG、ACK、PSH、RST、SYN、FIN 含义
  7. python笔记之发送邮件
  8. CPU 指令集(Instruction Set Architecture, ISA)
  9. 初级模拟电路:3-1 BJT概述
  10. 表单enctype属性传值问题