本文主要是介绍POJ1703 两种方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
找规律算出子节点与父节点，子节点与爷爷节点的关系来建图。/*
D
Accepted
916 KB
329 ms
C++
1120 B
2013-04-08 18:29:33
*/
#include<cstdio>const int maxn = 100000+10;int p[maxn]; //存父亲节点
int r[maxn]; //存与根节点的关系，0 代表同类， 1代表不同类int find(int x) //找根节点
{if(x == p[x]) return x;int t = p[x]; //记录父亲节点 方便下面更新r[]p[x] = find(p[x]);r[x] = (r[x]+r[t])%2; //根据子节点与父亲节点的关系和父节点与爷爷节点的关系，推导子节点与爷爷节点的关系return p[x]; //容易忘记
}void Union(int x, int y)
{int fx = find(x); //x所在集合的根节点int fy = find(y);p[fx] = fy; //合并r[fx] = (r[x]+1+r[y])%2; //fx与x关系 + x与y的关系 + y与fy的关系 = fx与fy的关系
}
void set(int n)
{for(int x = 1; x <= n; x++){p[x] = x; //自己是自己的父节点r[x] = 0; //自己和自己属于同一类}
}int main()
{int T;int n, m;scanf("%d", &T);while(T--){scanf("%d%d%*c", &n, &m);set(n);char c;int x, y;while(m--){scanf("%c%d%d%*c", &c, &x, &y); //注意输入//printf("%c\n", c);if(c == 'A'){if(find(x) == find(y)) //如果根节点相同，则表示能判断关系{if(r[x] != r[y]) printf("In different gangs.\n");else printf("In the same gang.\n");}else printf("Not sure yet.\n");}else if(c == 'D'){Union(x, y);}}}return 0;
}
一种是直接压缩路径，然后+N了区分不同帮派。
#include<cstdio>const int maxn = 100000+10;int p[maxn]; //存父亲节点
int r[maxn]; //存与根节点的关系，0 代表同类， 1代表不同类int find(int x) //找根节点
{if(x == p[x]) return x;int t = p[x]; //记录父亲节点 方便下面更新r[]p[x] = find(p[x]);r[x] = (r[x]+r[t])%2; //根据子节点与父亲节点的关系和父节点与爷爷节点的关系，推导子节点与爷爷节点的关系return p[x]; //容易忘记
}void Union(int x, int y)
{int fx = find(x); //x所在集合的根节点int fy = find(y);p[fx] = fy; //合并r[fx] = (r[x]+1+r[y])%2; //fx与x关系 + x与y的关系 + y与fy的关系 = fx与fy的关系
}
void set(int n)
{for(int x = 1; x <= n; x++){p[x] = x; //自己是自己的父节点r[x] = 0; //自己和自己属于同一类}
}int main()
{int T;int n, m;scanf("%d", &T);while(T--){scanf("%d%d%*c", &n, &m);set(n);char c;int x, y;while(m--){scanf("%c%d%d%*c", &c, &x, &y); //注意输入//printf("%c\n", c);if(c == 'A'){if(find(x) == find(y)) //如果根节点相同，则表示能判断关系{if(r[x] != r[y]) printf("In different gangs.\n");else printf("In the same gang.\n");}else printf("Not sure yet.\n");}else if(c == 'D'){Union(x, y);}}}return 0;
}这篇关于POJ1703 两种方法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
