[ABC238E]Rcange Sums

前言

一道水得不能再水的题，虽说在图论的题单里，但我真的没有用图，用了并查集就轻松\(AC\)。

大意

输入\(q\)个\(l,r\)，表示知道\(l\)到\(r\)的区间，最后问能不能知道\(0\)到\(n\)，能就输出Yes，不能就输出No。

思路

1. 图论做法：可以把知道\(l\)到\(r\)的区间抽象为从\(l-1\)向\(r\)连一条边，把从\(x\)到\(y\)有一条边理解为知道\(x+1\)到\(y\)的区间，最后从\(0\)开始，遍历整个图，看看能否到\(n\)就可以了。
2. 并查集做法：可以把知道\(l\)到\(r\)的区间抽象为\(l-1\)是\(r\)的祖先，最后看看\(0\)和\(n\)是否拥有公共祖先就可以了。

Code

图论：

不放了，网上到处都是(其实是我懒得写)。

并查集：

#include<bits/stdc++.h>
int n,q,l,r,pre[2000005];
inline int find(int x){
	return pre[x]==x?x:pre[x]=find(pre[x]);//查询
}
int main(){
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;++i)pre[i]=i;//初始化
	while (q--){
		scanf("%d%d",&l,&r);
		pre[find(l-1)]=find(r);//合并
	}
	if (find(0)==find(n))puts("Yes");
	else puts("No");
}