这道题的关键，就是将题目转化为图论。我们将每张牌的正反两面的数值连一条边，可以发现，我们只能在一棵树中选n-1个点。那么就意味着，当一个询问包含一整棵树时，这是不可能的（因为是用数值做编号，可以发现一个点只可能出现在一棵树中）。
那么如何实现呢？我们处理出每棵树的min和max，自然，树的其他所有节点都会包含在这一区间内。
#include<cstdio> #include<cctype> #include<vector> #include<iostream> using namespace std; const int N = 1e5 + 2; int n, k, Q, minr[N], sum, bian, maxx, minn; bool vis[N]; vector <int> G[N]; void read(int &x) { x = 0; char s = getchar(); while(! isdigit(s)) s = getchar(); while(isdigit(s)) { x = (x << 1) + (x << 3) + s - '0'; s = getchar(); } } void dfs(const int x) { vis[x] = 1; bian += G[x].size(); sum ++; maxx = max(maxx, x); minn = min(minn, x); for(int i = 0; i < G[x].size(); i ++) { int v = G[x][i]; if(vis[v]) continue; dfs(v); } } int main() { int a, b; read(n); read(k); for(int i = 1; i <= k; i ++) { read(a); read(b); G[a].push_back(b); G[b].push_back(a); } for(int i = 1; i <= n; i ++) minr[i] = n + 1; for(int i = 1; i <= n; i ++) { if(G[i].empty()) minr[i] = i;//一个点也是一棵树 else if(! vis[i]) { maxx = 1; minn = n; bian = sum = 0; dfs(i); bian >>= 1; if(bian == sum - 1) minr[minn] = maxx; } } for(int i = n - 1; i >= 1; i --)//意义：i+1--minr[i+1]可能被本区间包含，这时minr可以向内更进一步 minr[i] = min(minr[i], minr[i + 1]); read(Q); while(Q --) { read(a); read(b); if(minr[a] <= b) puts("No"); else puts("Yes"); } return 0; }谢谢！
