Analysis: Party Invitations by Fatih Gelgi

This is a fairly easy silver problem. A straightforward idea is to simulate the rules using a queue for inviting cows:
1. Add cow #1 to queue (cow #1 is invited as a constraint)
2. Get cow x from queue
3. Remove cow x from all groups
4. If there is a group that has only one remaining cow, add the cow to queue (the cow is invited)
5. Go to step 2 until there are no more cows in queue
Here, the critical step is 3. Removal operation has to be done fast. To determine the groups a cow, an inverse index can be used. In addition, sets can be used to hold each group. In this case, each removal operation will take O(log N) time. Since each cow is removed at most once, the time complexity will be O(N log N). Below is a sample solution:
```#include <fstream>
#include <set>
#include <queue>
#include <vector>

using namespace std;

#define MAXN 1000000

int n,g,cnt;
bool invited[MAXN];
vector<set<int> > groups;
vector<int> inverse[MAXN];
queue<int> q;

int main()
{
ifstream fin("invite.in");
fin >> n >> g;
for (int i=0; i<g; i++)
{
int s,k;
fin >> s;
set<int> gr;
for (int j=0; j<s; j++)
{
fin >> k;
gr.insert(--k);
// create an inverse index: the groups that a cow belongs
inverse[k].push_back(i);
}
groups.push_back(gr);
}
fin.close();

q.push(0);
invited[0]=true;
while (!q.empty())
{
int k=q.front();
q.pop();
cnt++;
// remove the invited cow from all groups
for (int j=0; j<inverse[k].size(); j++)
{
int x=inverse[k][j];
groups[x].erase(k);
// group constraint: invite the cow if she is the only uninvited
if (groups[x].size()==1)
{
int y=*(groups[x].begin());
if (!invited[y])
{
invited[y]=true;
q.push(y);
}
}
}
}

ofstream fout("invite.out");
fout << cnt << "\n";
fout.close();
}
```