个人做网站名称可以随意更改吗,国内优秀企业网站,国内有名的软件开发公司排名,服务器网站网站专用本题链接#xff1a;登录—专业IT笔试面试备考平台_牛客网登录—专业IT笔试面试备考平台_牛客网登录—专业IT笔试面试备考平台_牛客网
题目#xff1a; 样例#xff1a; 输入 5 5
1 1 2
3 1 2
2 2 4
3 1 4
3 2 5 输出 YES YES NO 思路#xff1a; 根据题意#xff0c;这…本题链接登录—专业IT笔试面试备考平台_牛客网登录—专业IT笔试面试备考平台_牛客网登录—专业IT笔试面试备考平台_牛客网
题目 样例
输入 5 5
1 1 2
3 1 2
2 2 4
3 1 4
3 2 5
输出 YES YES NO 思路 根据题意这是个模板的并查集但是多了一个操作就是合并区间多个元素为一个集合。 其中合并区间多个元素为一个集合的核心是存一个区间合并的 ne 数组。
初始化操作
// 初始化操作
inline Init()
{for(int i 1;i n ;i) f[i] i,ne[i] i 1;
}
多个元素区间合并操作
int L a,R b;
int t ne[L];
for(int i L ;i R;i t)
{Union(i,R);t ne[i];ne[i] ne[R];
} 具体合并优化过程跟着代码在草稿纸上模拟走一遍就思路清晰了。
AC代码如下
#include iostream
#include vector
#include queue
#include cmath
#include cstring
#include algorithm
#include unordered_map
#define endl \n
#define x first
#define y second
#define int long long
#define YES puts(YES)
#define NO puts(NO)
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,Ofast,inline)
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N 2e6 10;
inline void solve();signed main()
{
// freopen(a.txt, r, stdin);IOS;int _t 1;
// cin _t;while (_t--){solve();}return 0;
}int f[N],n,ne[N],m;
inline int Finds(int x)
{int t x;while(x ! f[x]) x f[x];f[t] x;return x;
}
inline void Union(int a,int b)
{a Finds(a),b Finds(b);f[a] b;
}
inline void Init()
{for(int i 1;i n;i) f[i] i,ne[i] i 1;
}
inline void solve()
{cin n m;Init();while(m--){int op,a,b;cin op a b;if(op 1) Union(a,b);else if(op 2){int L a,R b;int t ne[L];for(int i L ;i R;i t){Union(i,R);t ne[i];ne[i] ne[R];}}else{if(Finds(a) ! Finds(b)) NO;else YES;}}
} 最后提交
