voidmul1(){//求 矩阵 A 的 b 次方 memset(b,0,sizeof(b));for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)for(intk=1;k<=n;k++)b[i][j]+=a[i][j]*c[j][k];memcpy(a,b,sizeof(a));}voidmul2(){//自乘矩阵 n 行 n 列 memset(b,0,sizeof(b));for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)for(intk=1;k<=n;k++)b[i][j]+=c[i][k]*c[k][j];memcpy(c,b,sizeof(c));}voidpower(){while(b){if(b&1)mul1();mul2();b>>=1;}}
for(inti=1;i<=n;i++){memset(bo,0,sizeof(bo));if(dfs(i))ans++;}booldfs(intx){for(inti=1;i<=a[x][0];i++){// a 邻接表 if(!bo[a[x][i]]){if(find(link[a[x][i]])||link[a[x][i]]==0){//判断没有连过边或可以换 link[a[x][i]]=x;// 与右侧a[x][i]相连的为x return1;}}}return0;}
九、并查集
C++
1 2 3 4 5 6 7 8 9101112
voidff(){for(inti=1;i<=n;i++)fa[i]=i,r[i]=0;//r[i]表示以i为根的树的高度 }voidun(intx,inty){//find(x) 找 x 父亲intf1=find(x),f2=find(y);if(f1==f2)return;if(r[f1]==r[f2])r[f2]++,fa[f1]=f2;elseif(r[f1]>r[f2])fa[f2]=f1;elsefa[f1]=f2;}