D - Association for Control Over Minds(Kattis - control )

You are the boss of ACM (Association for Control over Minds), an upstanding company with a single goal of world domination.

Yesterday, you woke up, and saw that the weather was clear, and the birds were singing. “Another day, another world domination plan”, you sang to yourself as you devised your next world domination plan involving the illusory mind control potions.

There’s only one insignificant problem you have to solve before you can execute this perfection of a plan: you don’t know the correct recipe for the mind control potion. You asked the local Panda-breed brewmaster for the recipe, but unfortunately he didn’t know either. Instead, he gave you the mysterious tome titled The Root of all Evil (written by Halim the White). You read the evil book under candle light, and wrote down all the potion recipes contained inside the book. “One of them must be the formula for the mind control potion, I’m sure of it!”, you said to yourself. You numbered these recipes from 1 1 1 through N N N. “I just need to try concocting all of these recipes!”, you hummed to yourself.

Today, you woke up, and saw that the weather was clear, and…, anyway. You have purchased all the utensils and ingredients from the local grocery — onion, carrot, broom, vials, cauldrons, bat wings, …, all common grocery items. Now, you are ready to begin your experiments, but then you notice that some of the recipes share common ingredients! Unfortunately, you only bought one of each ingredient with you. “Oh no! What should I do now?!”, you panicked.

“I’ll just create some of the potions today, and do the remaining ones later.”, you resolved. You consider all your recipes one by one in order by their number from recipe 1 1 1 through recipe N N N. For each recipe, if you are not able to concoct this potion (explained in the next paragraph), you skip this recipe, and consider the next one, if any. Otherwise, even though it may cause some of the next potions to no longer be concoctable, you concoct this recipe. Thus, whether to concoct a potion is not a choice. It’s simply determined by whether it is possible or not to do so when you consider the potion.

In order to concoct a potion, you first prepare a new empty cauldron (you managed to procure an infinite number of cauldrons from the grocery store). Then, you combine all of the ingredients required for this potion and nothing else in this cauldron (that is, the cauldron cannot contain any ingredients not listed in the recipe). For the ingredients that have not been used for any of the previous potions that you’ve decided to concoct, you can simply put it into this cauldron. You can also pour the entire content of the cauldron used for one of your previous concoctions into this cauldron, thus mixing in all of the ingredients contained inside the cauldron (since you pour all of the content of the cauldron, this previous concoction can no longer be used for any of your next concoctions). Finally, you stir this cauldron with your broom and take a vial of the concoction to test on your minions later. The remaining concoction remains in this cauldron, and can be poured into another cauldron later.

“What is the number of recipes you will concoct this way today?”, you asked yourself.

Input

The first line contains a non-negative integer 2 ≤ N ≤ 200   000 2 \leq N \leq 200\, 000 2≤N≤200000, giving the total number of recipes you have. Thereafter follow N N N lines, the i i i-th line describes recipe number i i i. Each of these lines is a single space separated list of integers. Each of these lines begins with an integer 1 ≤ M 1 \leq M 1≤M, denoting the number of ingredients required to make this recipe. Then, M M M integers follow, describing the required ingredients. The ingredients are identified by integers between 0 0 0 and 500   000 500\, 000 500000, inclusively, with different integers denoting different ingredients. For each recipe, all of its ingredients will be distinct. The sum of M M M over all recipes will be no greater than 500   000 500\, 000 500000.

Output

Print the number of recipes you will concoct.

Sample Data Explanation

In the first example, the first potion can be concocted, since both ingredients were not used so far. Thus, you will concoct this potion. The second potion will also be concocted for the same reason. The third potion cannot be concocted, since ingredient 1 1 1 is no longer present, and is inside a cauldron mixed with another ingredient not present in the recipe. The fourth potion can be concocted by pouring the content of the cauldrons used for the first and second concoctions, and then adding ingredient 5 5 5, which has remained unused so far. The last potion cannot be concocted, since the content of the cauldron for the first potion has all been poured when making the fourth potion and thus is now mixed with other ingredients not present in the recipe.

For the second example, since the first potion can be concocted, it has to be concocted. Thus, the second and third potions can no longer be concocted.

Sample Input 1
5
2 1 2
2 3 4
2 1 5
5 1 2 3 4 5
2 1 2
Sample Output 1
3
Sample Input 2
3
2 1 2
1 1
1 2
Sample Output 2
1
题意：题目很长，大体的意思就是配药过程，按照顺序配药，每次考虑的时候只需考虑当前情况下能不能配成这种药，如果能的话配药即可，如果不能的话，跳到下一个，配药的规则是如果当前所需的原料没有被使用过直接放入锅中（每种原料只可使用一次），当前的原料部分是之前配过的配方，也可直接拿来使用，下面分析一组样例。
样例 分析
2 1 2 1,2均未被使用过，直接放入ans++
2 3 4 同上 ，ans++
2 1 5 1已经被使用过，无法使用
5 1 2 3 4 5 5 未被使用，直接放入，12 34 分别都在上面配到过，可以使用
2 1 2 1 2 在上面已经被使用过，切当前仅有的配过的配方是12345，
所以不可使用。
题解：结题思路就是带权并查集+STL，我们可以把每次使用的配方都并起来，然后，每次判断的时候如果可以由多个或一个集合合并得到，就让ans++，然后将相应的集合合并。
具体操作：可以将输入的每一组数据中的每一个点的父节点放入一个容器中（这里建议用set，因为set可以自动去除重复节点），这里判断能否合并的方法就是看放到set里的根节点的权（这里指的是并查集合中元素的数量）之和，能否等于输入元素的数量。
这里可以将方法简单的证明一下：
1：
假设有一个父节点的部分元素（而不是全部元素）在集合，则结果是大于输入元素的数量的，例如：
假设当前的并查集中元素父节点：1：3 4 5 6
2：7 8 9
10：11 12
假设输入的元素为1 3 4 5 6 7 10 11 12 ，很明显7 这个并查集合中的元素仅有部分在输入的元素中，那么元素数量和就是大于输入元素数量的，是不对的，回到题意就是7这个元素已经在之前用到过，所以无法进行操作。
这里，明显的还有就是在set集合中的元素数量之和是一定大于等于输入元素的数量的。
2：如果数量等于的话，那么就是符合答案的。
注：这里要注意的是值从0开始，建立并查集的时候注意。
下面是AC代码：

#include <bits/stdc++.h>
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define endl '\n'
#define ll long long int
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 7;

int pre[N], s[N];
int find(int x) {
    if (pre[x] == x)
        return x;
    return pre[x] = find(pre[x]);
}//并查集的查找操作，模板
void merge(int a, int b) {
    int p = find(a);
    int q = find(b);
    if (p != q) {
        pre[q] = p;
        s[p] += s[q];
    }
}//并查集的归并操作，这里归并的还有两个并查集元素数量也要归并
set<int> v;//set
signed main() {
    for (int i = 0; i <= N; i++)
        pre[i] = i, s[i] = 1;//初始化操作，从0开始
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        v.clear();//每一次输入的时候要清空，因为不需要遗留元素
        int m;
        cin >> m;
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;
            v.insert(find(x));//将各个元素的父节点放入集合中
        }
        int sum = 0;
        for (auto it = v.begin(); it != v.end(); it++)
            sum += s[*it];//加上父节点的所有元素个数
        if (sum == m) {
            cnt++;
            for (auto it = v.begin(); it != v.end(); it++)
                merge(*v.begin(), *it);//这是遍历容器合并的操作
        }
    }
    cout << cnt << endl;
    return 0;
}

总结：这道题的关键之处在于找到判断是否可以的方法，这里用到的带权并查集还是挺巧妙的。