link
并收集假货 一直调不对
题意
给定一张n个点m条边的无环无重边的有向图，初始是每个点都是白色，你可以选择一个点染黑，紧接着对于每个点来说，若他的入边的起点都被染黑，他也就会变成黑色
做法
如果是他的话 入度为1 然后染色前面的点 之后，你可以把它们看成一个整体 但这个过程显然不能暴力 我们可以用队列模拟 一个启发式合并log优化 注意一下swap我们必须交换他的东西 "pre"集合 (我的代码跑得不快，卡在时限上)
#include <bits/stdc .h> using namespace std; //#define int long long typedef long long ll; typedef pair<int,int> pii; #define x first #define y second #define pb push_back #define inf 1e18 #define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fer(i,a,b) for(int i=a;i<=b;i ) #define der(i,a,b) for(int i=a;i>=b;i--span class="token punctuation">)
const int maxn=1e5+10;
const int mod=1e9+7;
int qmi(int a,int b) {
int res=1;
while(b) {
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
const int N=2e5+10;
int dr[4][2]= {
{
-1,0},{
1,0},{
0,-1},{
0,1}};
int n,k;
int fa[N];
set<int>g[N]; //pre
set<int>e[N]; //to
int _;
int sz[N];
int ttt;
int ans;
int cnt;
int find(int x) {
return fa[x]==x?:fa[x]=find(fa[x]);
}
void solve() {
cin>>n;
fer(i,1,n)fa[i]=i, e[i].clear(),g[i].clear(),sz[i]=1;
fer(i,1,n) {
int t;
cin>>t;
while(t--) {
int x;
cin>>x;
e[x].insert(i);
g[i].insert(x);
}
}
queue<pii>q;
//fer(i,1,n)cout<<g[i].size()<<endl;
fer(i,1,n)if(g[i].size()==1)q.push({
i,*g[i].begin()});
// cout<<cnt<<"***"<<endl;
while(!q.empty()) {
int p1=q.front().first;
int p2=q.front().second;
q.pop();
int a=find(p1);
int b=find(p2);
if(a==b)continue;
if(e[a].size()>e[b].size())swap(a,b),swap(g[a],g[b]);
fa[a]=b;
sz[b]+=sz[a];
for(auto v:e[a]) {
int t=find(v);
if(t==b)continue;
e[b].insert(t);
g[t].erase(a);
g[t].insert(b);
if(g[t].size()==1)q.push({
t,b});
}
}
ans=0;
fer(i,1,n) {
// cout<<sz[find(i)];
ans=max(ans,sz[find(i)]);
}
cout << "Case #" <<++ ttt << ": " << ans << "\n";
}
int main() {
IOS;
cin>>_;
while(_--) solve();
return 0;
}