codeforces 320B（dfs）
题意描述
In this problem at each moment you have a set of intervals. You can move from interval (a, b) from our set to interval (c, d) from our set if and only if c < a < d or c < b < d. Also there is a path from interval I 1 from our set to interval I 2 from our set if there is a sequence of successive moves starting from I 1 so that we can reach I 2.
Your program should handle the queries of the following two types:
“1 x y” (x < y) — add the new interval (x, y) to the set of intervals. The length of the new interval is guaranteed to be strictly greater than all the previous intervals. “2 a b” (a ≠ b) — answer the question: is there a path from a-th (one-based) added interval to b-th (one-based) added interval? Answer all the queries. Note, that initially you have an empty set of intervals.
定义两个操作，1操作是添加区间到集合，2操作是判断两个点是否连通，连通的条件就是c < a < d || c < b < d。
思路
这道题的难点在于读懂题意，读懂题意后就很容易做了，每次询问可以用dfs判断两个点是否连通
AC代码
#include<bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=1005;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
int n,idx=1;
struct node{
int a,b;
}Node[N];
bool used[N];
void dfs(int u){
used[u]=true;
for(int i=1;i<=idx;i++){
if(used[i]) continue;
if((Node[i].a < Node[u].a && Node[i].b > Node[u].a) || (Node[u].b > Node[i].a && Node[u].b < Node[i].b)){
dfs(i);
}
}
}
void solve(){
cin>>n;
for(int i=0;i<n;i++){
int op,x,y;cin>>op>>x>>y;
if(op==1){
Node[idx].a=x;
Node[idx].b=y;
idx++;
}
if(op==2){
memset(used,0,sizeof used);
dfs(x);
if(used[y]) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
}
int main(){
IOS;
solve();
return 0;
}腾讯云开发者
