自动搬运

查看原文

来自洛谷，原作者为

	宁_缺 毕竟几人真得鹿，不知终日梦为鱼。

搬运于2025-08-24 21:31:36，当前版本为作者最后更新于2019-10-17 21:24:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

两个月前过的二分图模板，没想到两个月后又能在这里邂逅几乎一模一样的题（反正我没看出区别），那就发篇题解纪念吧

二分图压压行真的很短（至少比SPFA、BSGS短多了）

就像这样：

#include<bits/stdc++.h>
const int N=201;
int n,m,lk[N],g[N][N],v[N],ans;
bool dfs(int now){
	for(int i=1;i<=n;i++)
		if(!v[i]&&g[now][i]&&(v[i]=1))//其实在&&中修改变量还是挺方便的
			if((!lk[i]||dfs(lk[i]))&&(lk[i]=now))return 1;//与或非优先级懒得算了，于是搞了一堆括号
	return false;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,s,x;i<=n;i++){
		scanf("%d",&s);
		while(s--)scanf("%d",&x),g[i][x]=1;
	}
	for(int i=1;i<=n;i++)
		memset(v,0,sizeof(v)),ans+=dfs(i);
	return 0*printf("%d",ans);
}

开学后发的第一篇题解（看我多懒）