CodeForces - 320B Ping-Pong (Easy Version)

 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\n");
53             else printf("NO\n");
54         }
55     }
56     return 0;
57 }