对联通块做背包即可。
最坏复杂度是 sqrt(n) * n * logw的，并且logw很小为常数。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> //#define int long long using namespace std; const int N=1e5+10; int n,m,dp[N],cnt[N],vis[N],num; vector<int> g[N]; void dfs(int x){ vis[x]=1; num++; for(int to:g[x]) if(!vis[to]) dfs(to); } inline int check(int x){ while(x){ if(x%10!=4&&x%10!=7) return 0; x/=10; } return 1; } signed main(){ cin>>n>>m; for(int i=1,a,b;i<=m;i++) scanf("%d %d",&a,&b),g[a].push_back(b),g[b].push_back(a); for(int i=1;i<=n;i++) if(!vis[i]) num=0,dfs(i),cnt[num]++; memset(dp,0x3f,sizeof dp); dp[0]=0; for(int i=1;i<=n;i++) if(cnt[i]){ int j=1; while(j<=cnt[i]){ cnt[i]-=j; for(int k=n;k>=j*i;k--) dp[k]=min(dp[k],dp[k-j*i]+j); j*=2; } if(cnt[i]){ for(int k=n;k>=cnt[i]*i;k--) dp[k]=min(dp[k],dp[k-cnt[i]*i]+cnt[i]); } } int res=1e9; for(int i=1;i<=n;i++) if(check(i)) res=min(res,dp[i]-1); if(res>=1e8) res=-1; cout<<res; return 0; }