并查集 poj1611&poj2492

poj1611 简单题

代码中id记录父节点,sz记录子树规模。一个集合为一棵树。

#include <iostream>
#include <cstdio>
using namespace std; int id[300005];
int sz[300005]; void add(int a, int b)
{
int i, j;
for (i = a; i != id[i]; i = id[i]);
for (j = b; j != id[b]; j = id[j]);
if (i == j) return;
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
} else {
id[j] = i;
sz[i] += sz[j];
}
} int main()
{
int n, m, cnt, root, temp;
while (scanf("%d%d", &n, &m) != EOF) {
if (!n) break;
for (int i = 0; i < n; ++i) {
id[i] = i;
sz[i] = 1;
}
for (int i = 0; i < m; ++i) {
scanf("%d", &cnt);
scanf("%d", &root);
for (int j = 1; j < cnt; ++j) {
scanf("%d", &temp);
add(root, temp);
}
}
int ans = 0;
int rt;
for (rt = 0; rt != id[rt]; rt = id[rt]);
for (int i = 0; i < n; ++i) {
int j;
for (j = i; j != id[j]; j = id[j]);
if (j == rt) ++ans;
}
printf("%d\n", ans);
}
return 0;
}

  

poj 2492

题目也是醉了,看半天没看懂= =#

输入每对a b表示a和b是夫妻,问有没有同性恋= =

把每一次a b放入同一集合,并用rel记录每个节点和它父节点的相对关系。这样同一集合的任意两点间关系就确定了

/**********************************************
Memory: 8500 KB Time: 125 MS
Language: G++ Result: Accepted
***********************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; int id[2010], sz[2010];
int a[1000005], b[1000005];
int rel[2010]; //和父节点的性别是否一致,一致为0,否则为1 int Scan() { //输入外挂
int res = 0, flag = 0;
char ch;
if((ch = getchar()) == '-') flag = 1;
else if(ch >= '0' && ch <= '9') res = ch - '0';
while((ch = getchar()) >= '0' && ch <= '9')
res = res * 10 + (ch - '0');
return flag ? -res : res;
} void add(int a, int b)
{
int i, j;
int rel_a = 0, rel_b = 0;
for (i = a; i != id[i]; i = id[i])
rel_a = (rel_a + rel[i]) % 2;  //a和根节点的关系
for (j = b; j != id[j]; j = id[j])
rel_b = (rel_b + rel[j]) % 2;  //b和根节点的关系
if (i == j) return ;
if (sz[i] <= sz[j]) { //i->j
sz[j] += sz[i];
id[i] = j;
rel[i] = (rel_a == rel_b) ? 1 : 0; } else { //j->i
sz[i] += sz[j];
id[j] = i;
rel[j] = (rel_a == rel_b) ? 1 : 0;
}
} int is_gay(int a, int b)
{
int i, j;
int rel_a = 0, rel_b = 0;
for (i = a; i != id[i]; i = id[i])
rel_a = (rel_a + rel[i]) % 2;
for (j = b; j != id[j]; j = id[j])
rel_b = (rel_b + rel[j]) % 2;
if (i == j && rel_a == rel_b)
return 1;
return 0;
} int main()
{
int t, m, n;
t = Scan();
for (int k = 1; k <= t; ++k) {
n = Scan();
m = Scan();
for (int i = 1; i <= n; ++i) {
id[i] = i;
sz[i] = 1;
rel[i] = 0;
}
for (int i = 0; i < m; ++i) {
a[i] = Scan();
b[i] = Scan();
add(a[i], b[i]);
}
int i;
for (i = 0; i < m; ++i) {
if (is_gay(a[i], b[i]))
break;
}
printf("Scenario #%d:\n%s\n\n", k, i == m ? "No suspicious bugs found!" : "Suspicious bugs found!");
}
return 0;
}

  

总结经验教训:以后多敲两行也不能复制粘贴= =太坑。。。

上一篇:[转]NHibernate之旅(3):探索查询之NHibernate查询语言(HQL)


下一篇:string类find函数返回值判定