P3068 [USACO13JAN]派对邀请函Party Invitations

这题用set就行了。

将每个组看成一个点，将每组中的牛与其连边

然后对于每个组开个set，然后将每组中的牛插入。

开个队列记录要删除的，首先进队的是1。ans为1。

从队首去取出1号牛开始删除将1所连的点中删除1，找到删完之后size为1的组，将剩余的一个牛加入队中，ans+1，依次从队中取，然后删。

然后知道队中无元素，输出ans就行。

#include<iostream>
#include<cstdio>
#include<set>
#include<queue>
using namespace std;
const int N=1000005;
int n,m,cnt,head[N],in[N],ans;
struct node{
    int to,nxt;
}e[N];
queue<int>q;
set<int> s[N];
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
inline void add(int from,int to){
    e[++cnt]=(node){to,head[from]};
    head[from]=cnt;
}
int main(){
    n=read();m=read();
    int x,y;
    for(int i=1;i<=m;++i){
        x=read();
        for(int j=1;j<=x;++j){
            y=read();
            add(y,i);
            s[i].insert(y);
        }
    }
    in[1]=1,ans=1;q.push(1);
    set<int>::iterator it;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=head[now];i;i=e[i].nxt){
            s[e[i].to].erase(now);
            if(s[e[i].to].size()==1){
                it=s[e[i].to].begin();
                if(!in[*it]){
                    in[*it]=1;
                    ans++;
                    q.push(*it);
                }
            }
        }
    }
    printf("%d",ans);
    return 0;
}