Posted on 2007-07-15 11:12
ZelluX 閱讀(478)
評論(0) 編輯 收藏 所屬分類:
Algorithm
突然想通了一開始一直超時的原因。
每次我都是把新的suspect并入第一個元素所在的集合中，但是由于使用了優(yōu)化后的并集操作，有可能是第一個元素所在的集合并入了新的suspect所在的集合，也就是說此后last變量并沒有指向第一個元素所在集合的跟結(jié)點。于是在Union方法中，parent[root1]可能得到一個正整數(shù)，并導(dǎo)致Find方法死循環(huán)（根結(jié)點的parent為正）
后來把Find方法放到Union方法中，問題解決了。
#include <iostream>
using namespace std;
const int DEFAULT_SIZE = 100;
class UFSets
{
private:
int *parent;
int size;
public:
UFSets(int s = DEFAULT_SIZE);
~UFSets() { delete [] parent; }
void Union(int root1, int root2);
int Find(int x);
void Clear(int n);
};
UFSets::UFSets(int s)
{
size = s;
parent = new int[size + 1];
for (int i = 0; i <= size; i++)
parent[i] = -1;
}
int UFSets::Find(int x)
{
int result = x;
while (parent[result] >= 0)
result = parent[result];
return result;
}
void UFSets::Union(int root1, int root2)
{
// The old version didn't contain the following 3 setences.
root1 = Find(root1);
root2 = Find(root2);
if (root1 == root2) return;
int temp = parent[root1] + parent[root2];
if (parent[root2] < parent[root1])
{
parent[root1] = root2;
parent[root2] = temp;
}
else
{
parent[root2] = root1;
parent[root1] = temp;
}
}
void UFSets::Clear(int n)
{
for (int i = 0; i < n; i++)
parent[i] = -1;
}
int main()
{
UFSets sets(30000);
int n, m;
while (true)
{
cin >> n >> m;
if (n == 0) break;
sets.Clear(n);
for (int i = 0; i < m; i++)
{
int t;
cin >> t;
int last, x;
cin >> last;
last = sets.Find(last);
for (int j = 1; j < t; j++)
{
cin >> x;
sets.Union(last, x);
// int temp = sets.Find(x);
// if (temp != last)
// sets.Union(last, temp);
}
}
int result = 1;
int target = sets.Find(0);
for (int i = 1; i < n; i++)
if (sets.Find(i) == target)
result ++;
cout << result << endl;
}
return 0;
}