vivaEleanor @ 2019-04-18 19:10:32
那位大佬能告诉蒟蒻我这有什么问题....
using namespace std; int N,M; int pre[10010]; int zi,xi,yi; int find(int root) { if(pre[root]=root)return root; return pre[root]=find(pre[root]); }
void join(int root1,int root2){ int x,y; x=find(root1); y=find(root2); if(x!=y) pre[x]=y; //合并
}
int main(){
cin>>N>>M;
cin>>zi>>xi>>yi;
int i,j;
int t1,t2;
if(zi=1){join(xi,yi);}
else {
t1=find(xi) ;
t2=find(yi);
if(t1==t2){cout<<"Y"<<endl;}
else{cout<<"N"<<endl;}
return 0;
}
}
by yyk504 @ 2019-04-18 19:33:30
@vivaEleanor 您现在是不是只会输出一个结果。。。
by NaCly_Fish @ 2019-04-18 19:33:58
这是我的代码，您可以参考一下：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#define ll long long
#define reg register
#define N 10003
#define ls son[u][0]
#define rs son[u][1]
using namespace std;
int n,m;
inline void read(int &x);
void print(int x);
struct Link_Cut_Tree{
int fa[N],son[N][2],s[N],st[N];
bool r[N];
inline bool isroot(int u){
return son[fa[u]][0]==u||son[fa[u]][1]==u;
}
inline void pushup(int u){
}
inline void pushr(int u){
swap(son[u][0],son[u][1]);
r[u] ^= 1;
}
inline void pushdown(int u){
if(!r[u]) return;
if(ls) pushr(ls);
if(rs) pushr(rs);
r[u] = 0;
}
inline int ident(int f,int u){
return son[f][1]==u;
}
inline void rotate(int u){
int y = fa[u],z = fa[y];
int k = ident(y,u),w = son[u][k^1];
if(isroot(y)) son[z][ident(z,y)] = u;
son[u][k^1] = y;
son[y][k] = w;
if(w) fa[w] = y;
fa[y] = u;
fa[u] = z;
pushup(y);
}
inline void splay(int u){
int y = u,z = 0;
st[++z] = y;
while(isroot(y)) st[++z] = y = fa[y];
while(z) pushdown(st[z--]);
while(isroot(u)){
y = fa[u];
z = fa[y];
if(isroot(y)){
if((son[y][0]==u)^(son[z][0]==y)) rotate(u);
else rotate(y);
}
rotate(u);
}
pushup(u);
}
inline void access(int u){
int y = 0;
while(u){
splay(u);
rs = y;
pushup(u);
y = u;
u = fa[u];
}
}
inline void makeroot(int u){
access(u),splay(u);
pushr(u);
}
inline int findroot(int u){
access(u),splay(u);
while(ls){
pushdown(u);
u = ls;
}
splay(u);
return u;
}
inline void split(int u,int v){
makeroot(u);
access(v),splay(v);
}
inline void link(int u,int v){
makeroot(u);
if(findroot(v)!=u) fa[u] = v;
}
inline void cut(int u,int v){
makeroot(u);
if(findroot(v)!=u||fa[v]!=u||son[v][0]) return;
fa[v] = son[u][1] = 0;
pushup(u);
}
inline int query(int u,int v){
split(u,v);
return s[v];
}
inline bool connected(int u,int v){
return findroot(u)==findroot(v);
}
}T;
signed main(){
int t,u,v;
read(n),read(m);
for(int i=1;i<=m;++i){
read(t),read(u),read(v);
if(t==1){
if(T.connected(u,v)) continue;
T.link(u,v);
}else
printf(T.connected(u,v)?"Y\n":"N\n");
}
return 0;
}
inline void read(int &x){
x = 0;
char c = getchar();
while(c<'0'||c>'9') c = getchar();
while(c>='0'&&c<='9'){
x = (x<<3)+(x<<1)+(c^48);
c = getchar();
}
}
void print(int x){
if(x>9) print(x/10);
putchar(x%10+'0');
}by Celestial_Scarlet @ 2019-04-18 19:34:00
by Celestial_Scarlet @ 2019-04-18 19:34:19
@NaCly_Fish 神鱼大招：劝退新人
by 花里心爱 @ 2019-04-18 19:35:04
@NaCly_Fish Orz 神仙不屑于写并查集
by vivaEleanor @ 2019-04-18 19:35:28
@yyk504 嗯嗯嗯嗯嗯嗯嗯嗯嗯嗯
by Eason_AC @ 2019-04-18 19:35:34
既然神鱼大佬都炸出来了，我也来安利一个自己的程序肯定比神鱼大佬的菜得多：
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define N 10005
using namespace std;
int father[N];
inline int fa(int x) {
if(father[x] != x) father[x] = fa(father[x]);
return father[x];
}
inline void unionn(int x, int y) {
x = fa(x), y = fa(y);
if(x == y) return;
father[y] = x;
return;
}
inline bool same(int x, int y) {
return fa(x) == fa(y);
}
int n, m;
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
father[i] = i;
for(int i = 1; i <= m; ++i) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if(a == 1) unionn(b, c);
else if(a == 2) {
if(same(b, c))
printf("Y\n");
else
printf("N\n");
}
}
return 0;
} by yyk504 @ 2019-04-18 19:35:39
@NaCly_Fish 蒟蒻表示膜拜
by F1aMiR3 @ 2019-04-18 19:36:11
@vivaEleanor 看了一下您的做题记录，建议您先去做一些新手村的题，等把语法学完了并且已经接触了一些数据结构再来做这题
by yyk504 @ 2019-04-18 19:36:47
@Eason_AC emmm。。。终于看见一个看得懂的正解了。。。