Analysis: Party Invitations by Fatih Gelgi
#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(); }