一个集合覆盖有关问题

一个集合覆盖问题
给定一组集合S1，S2，。。Sn，其满足：对任意一个集合Si（1<=i<=n），存在Sj使得Si与Sj的交集不为空。
求：从S1，S2，。。Sn选择x个互不相交的集合，使得这x个集合的并集包含的元素最多。
请给出算法的基本思路。 算法
[解决办法]
考虑：
（1）根据集合元素从多到少对集合进行排序，记排序之后的集合分别为s[0],...,s[n-1]，复杂度O(nlogn)
（2）判断s[i]与s[j]是否相交，记录在intersected[n][n]（初始化全为false）中，这里记录是有向的，即i<j且s[i]s[j]，则只记录intersected[i][j] = true
（3）判断有向图是否有环，如果

[解决办法]
不好意思，刚有点事情，可以这么考虑（仅供参考）
考虑：
（1）根据集合元素从多到少对集合进行排序，记排序之后的集合分别为s[0],...,s[n-1]，复杂度为(nlogn);

（2）判断s[i]与s[j]是否相交，记录在intersected[n][n]（初始化全为false）中，这里记录是有向的，即i<j且s[i]s[j]相交，则只记录intersected[i][j] = true，复杂度为O(n*n*sizeof(s[0]));

（3）构造图：intersected[i][j] = true时，构造s[i]到s[j]的一条边(由于对任意一个集合Si，存在Sj使得Si与Sj的交集不为空，所以不存在孤立节点)，把构造的有向图当做无向图来判断是否有环;

（4）如果没有，则是多叉树的结构，可以dp，事实上此时问题化为最大独立集问题，状态转移方程如下：

maxUnionSize[i] = max{       //maxUnionSize[i]表示根节点是i时，X的最大size
sum{maxUnionSize[j], j is i's child},                  //do not chose s[i], chose its chilren
s[i].size() + sum{maxUnionSize[k], k is i's grandchild}//chose s[i] and its' grandchilren
}

int sumSize[n];  //sumSize[i] = sum(s[j].size()), j=i+1,...,n-1且interseced[i][j] = true
bool canNotBeChosen[n] = {0};  //初始化全部集合都为可选状态
int maxUnionSize = s[0].size();//初始化为最大集合的元素个数
void backtrace(int index, int sum)
{
    if(index >= n){
        if(sum > maxUnionSize) maxUnionSize = sum;
        return;
    }

    if(!canNotBeChosen[index]){         //s[index]可选，则选中s[index]
        markAdjOptional(index, false);  //标记相交的集合不可选
        backtrace(index+1, sum+s[index].size());
        markAdjOptional(index, true);   //标记相交的集合可选
    }
    //不选s[index]
    if(sum + sumSize[index] > maxUnionSize) backtrace(index+1, sum);//如果可能存在更大选法
}