Send 题（send）
【题目描述】 某个国家有??座城市，一开始，这??座城市之间没有道路联通。 需要支持两个操作： ① 在城市??到城市??之间加入一条长度为??的道路。 ② 询问是否存在一条从城市??到城市??的长度为偶数的路径。
【输入格式】 第一行包含两个正整数??, ??表示城市个数和操作个数。 接下来??行，每行包含四个数??, ??, ??, ??。 当?? = 1 时，表示在城市??到城市??之间加入一条长度为??的道路。 当?? = 2 时，表示询问是否存在一条从城市??到城市??的长度为偶 数的路径，此时，??总是 1；
【输出格式】 输出文件包括若干行，表示你的程序对②操作的回答，若存在一条 从城市??到 城市??的长度为偶数的路径，输出 YES，否则输出 NO。
【样例输入】
5 9
1 1 2 3
1 1 3 2
1 3 5 5
2 1 5 1
2 2 5 1
1 2 4 4
1 1 4 6
2 1 5 1
2 3 5 1
【样例输出】
NO
YES
YES
YES
n,q<=1e5
sol：种类并查集，挺好写的
#include <bits/stdc++.h> using namespace std; typedef int ll; inline ll read() { ll s=0; bool f=0; char ch=‘ ‘; while(!isdigit(ch)) { f|=(ch==‘-‘); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) { if(x<0) { putchar(‘-‘); x=-x; } if(x<10) { putchar(x+‘0‘); return; } write(x/10); putchar((x%10)+‘0‘); return; } #define W(x) write(x),putchar(‘ ‘) #define Wl(x) write(x),putchar(‘\n‘) const int N=200005; int n,Q; int fa[N]; inline int gf(int x) { return (fa[x]==x)?x:(fa[x]=gf(fa[x])); } inline void Ubbon(int x,int y) { int fx=gf(x),fy=gf(y); fa[fx]=fy; } int main() { freopen("send.in","r",stdin); freopen("send.out","w",stdout); int i,opt,x,y,z; R(n); R(Q); for(i=1;i<=(n<<1);i++) fa[i]=i; while(Q--) { R(opt); R(x); R(y); R(z); if(opt==1) { if(z&1) {Ubbon(x,y+n); Ubbon(x+n,y);} else {Ubbon(x,y); Ubbon(x+n,y+n);} } else { int fx=gf(x),fy=gf(y); (fx==fy)?puts("YES"):puts("NO"); } } return 0; } /* input 5 9 1 1 2 3 1 1 3 2 1 3 5 5 2 1 5 1 2 2 5 1 1 2 4 4 1 1 4 6 2 1 5 1 2 3 5 1 output NO YES YES YES */
原文：https://www.cnblogs.com/gaojunonly1/p/11185771.html
