CodeForces

题目最开始完全不懂配合案例也看不懂-_-

总之就是用传递性问能否从a区间到b区间

dfs(x,y) 走遍与第x区间所有的联通区间最后检验第y区是否被访问过

是一道搜索好题搜索还需加强

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 
 5 using namespace std;
 6 
 7 typedef long long ll;
 8 typedef pair<ll,ll> P;
 9 int N,n = 0;//record how many intervals
10 bool vis[108];
11 P p[108];
12 
13 
14 bool check(int x, int y)
15 {
16     return ( (p[x].first < p[y].second && p[x].first > p[y].first) || (p[x].second < p[y].second && p[x].second > p[y].first) );
17 }
18 
19 void dfs(int x, int y)//x-->>start interval; y-->>end interval 把所有与x联通的区间都走一遍
20 {
21     //if(x == n) return false;//
22     if ( vis[x] || vis[y] ) return ;
23     vis[x] = true;//经过了x
24     for (int i = 0; i < n; i++)
25     {
26         if (vis[i]) continue;//hes been visited
27         if ( check(x, i) )//之前版本 if (dfs(x,i) && dfs(i,Y) return true;//每次进函数都会找 x连通的
28         {
29             dfs(i, y);
30         } //不需要dfs(x,i) check即可 因为 跳转到dfs(i, y ) 小看了dfs()想多了
31     }
32     return ;//最终只需要检查 vis[b]即可 ->b是否被走过
33 }
34 int main()
35 {
36     int query, a, b;
37     freopen("in.txt", "r", stdin);
38     scanf("%d", &N);
39     for (int i = 0; i < N; i++)
40     {
41         scanf("%d%d%d", &query, &a, &b);
42         if (query == 1)
43         {
44             p[n].first = a;
45             p[n].second = b;
46             n++;
47         }
48         else if (query == 2)
49         {
50             memset(vis, 0, sizeof(vis));
51             dfs(a-1, b-1);
52             if (vis[b-1]) printf("YES
");
53             else printf("NO
");
54         }
55     }
56     return 0;
57 }

同样的这道题用bfs也可以做

理解一下 dfs和bfs的区别

dfs-->> 一条路走到黑知道无法走然后再走另外一条路

如果正确结果在最后一个分支那么相当于就是把所有可能都遍历了一遍

bfs-->> 每条路都先走第一步到下一个点后又走下一层的所有第一步这样每一次都想外扩展

因为每次都是走第一步每一个节点都向下一层扩展一层所以可以找到最短路径

bfs :

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <queue>
 5 //bfs解F题
 6 using namespace std;
 7 
 8 typedef pair<long long, long long> P;
 9 P interval[128];
10 int T, num = 0;
11 bool vis[128];
12 
13 bool check(int x, int y)
14 {
15     if ( interval[x].first > interval[y].first && interval[x].first < interval[y].second || interval[x].second > interval[y].first && interval[x].second < interval[y].second)
16     return true;
17     return false;
18 }
19 
20 bool bfs(int x, int y)
21 {
22     queue<int> que;
23     que.push(x);
24     while(!que.empty())
25     {
26         int tx = que.front();
27         P crt = interval[tx];
28         que.pop();
29         if (vis[tx]) continue;
30         vis[tx] = true;
31         if ( check(tx, y) ) return true;
32         for (int i = 0; i < num; i++)
33         {
34             if (check(tx, i) && !vis[i])
35             {
36                 que.push(i);
37             }
38         }
39     }
40     return false;
41 
42 }
43 
44 
45 int main()
46 {
47     freopen("in.txt", "r", stdin);
48     scanf("%d", &T);
49     int cas, a, b;
50     while (T--)
51     {
52         memset(vis, 0, sizeof(vis));
53         scanf("%d%d%d", &cas, &a, &b);
54         if(cas == 1)
55         {
56             interval[num].first = a;
57             interval[num].second = b;
58             num++;
59         }
60         else
61         {
62             if (bfs(a-1, b-1)) printf("YES
");
63             else printf("NO
");
64         }
65     }
66     return 0;
67 }