SDUT OJ 2138 BFS 判断可达性 2139 BFS 从起始点到目标点的最短步数

BFS 判断可达性邻接vector存储

 1 # include <iostream>
 2 # include <algorithm>
 3 # include <queue>
 4 # include <string.h>
 5 # include <vector>
 6 # define N 1010
 7 using namespace std;
 8 
 9 bool vis[N];
10 vector<int>G[N];
11 
12 void add(int u, int v)
13 {
14     G[u].push_back(v);
15 }
16 
17 bool BFS(int s)
18 {
19     queue<int>q;
20     q.push(s);
21     vis[s] = true;
22     while(!q.empty())
23     {
24         int u = q.front();
25         vis[u] = true;
26         q.pop();
27         for(int i = 0; i < (int)G[u].size(); i++)
28         {
29             int v = G[u][i];
30             if(!vis[v])
31             {
32                 q.push(v);
33                 vis[v] = true;
34                 if(v == 1)
35                     return true;
36             }
37         }
38     }
39     return false;
40 }
41 
42 int main(void)
43 {
44     int n, m;
45     while(cin >> n >> m)
46     {
47         memset(vis, 0, sizeof(vis));
48         for(int i = 0; i <= n; i++)
49             G[i].clear();
50         for(int i = 0; i < m; i++)
51         {
52             int u, v;
53             cin >> u >> v;
54             add(u, v);
55         }
56         if(BFS(n))
57             cout << "YES" << endl;
58         else
59             cout << "NO" << endl;
60     }
61 
62     return 0;
63 }

View Code

BFS 从起始点到目标点的最短步数邻接vector存储

 1 # include <iostream>
 2 # include <algorithm>
 3 # include <queue>
 4 # include <string.h>
 5 # include <vector>
 6 # define N 1010
 7 using namespace std;
 8 
 9 bool vis[N];
10 vector<int>G[N];
11 
12 struct node
13 {
14     int v, cnt;
15 } ;
16 
17 void add(int u, int v)
18 {
19     G[u].push_back(v);
20 }
21 
22 int BFS(int s)
23 {
24     queue<node>q;
25     node p;
26     p.v = s;
27     p.cnt = 0;
28     q.push(p);
29     vis[s] = true;
30     while(!q.empty())
31     {
32         node u = q.front();
33         vis[u.v] = true;
34         q.pop();
35         if(u.v == 1)
36             return u.cnt;
37         for(int i = 0; i < (int)G[u.v].size(); i++)
38         {
39             node k;
40             k.v = G[u.v][i];
41             k.cnt = u.cnt+1;
42             if(!vis[k.v])
43             {
44                 q.push(k);
45                 vis[k.v] = true;
46             }
47         }
48     }
49     return 0;
50 }
51 
52 int main(void)
53 {
54     int n, m;
55     while(cin >> n >> m)
56     {
57         memset(vis, 0, sizeof(vis));
58         for(int i = 0; i <= n; i++)
59             G[i].clear();
60         for(int i = 0; i < m; i++)
61         {
62             int u, v;
63             cin >> u >> v;
64             add(u, v);
65         }
66         int t = BFS(n);
67         if(!t)
68             cout << "NO" << endl;
69         else
70             cout << t << endl;
71     }
72 
73     return 0;
74 }

View Code