今天来水一波题解……
理解题意
由于题目意思讲得很清楚，就因为懒惰直接复制了……
给你一堆一对对的关系，然后每一个关系对代表两个人认识。然后你每次可以选择一个人i，让i认识的所有人都相互认识，即i把介绍自己所有的朋友给其他人。然后现在问你最少需要选择多少个这样的i，使得所有的人都相互认识。
注意了，朋友的朋友并不一定互为朋友，否则就用并查集秒了（这看颜色紫紫的就知道不是这样）。
思路
用状压DP
定义一个数组DP[s],s表示互为朋友的人的状态，例如101001表示第1个，第4个和第6个人的互为朋友，而DP[s]表示实现s这个状态所需的介绍次数。
状态转移方程：
dp[s|fr[i]]=min(dp[s|fr[i]],dp[s]+1);
dp[s|fr[i]]表示在状态s中，i介绍朋友后的状态，fr[i]表示i的朋友的集合，记住i也认识它自己！！！
那么初始化呢，因为i的朋友只需i来叫一次，so……fr[i]=1。
注意如果输入的关系即可使所有人互为朋友，则应输出0，要特判。
接下来贴上我丑陋的代码
ACcode
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=(1<<22)+1000;
int fr[N];//fr[i]-->i的朋友
int s[N];//人的集合
int dp[N];//使集合i的人认识所需介绍次数
int q[N];//q[s]=i表示s的转态这次由i介绍得到
int pre[N];//存s经过这次i介绍之前的状态
const int inf=0x3f3f3f3f;
void dfs(int x)
{
if(pre[x]) dfs(pre[x]);
cout<<q[x]<<" ";//在回溯时输出
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
memset(dp,0x3f,sizeof dp);
cin>>n>>m;
for(int i=1;i<=n;i++) fr[i]+=1<<(i-1);//自己认识自己
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
fr[u]+=1<<(v-1);
fr[v]+=1<<(u-1);
//v,u互为朋友
}
if(m==n*(n-1)/2)//原本互为朋友，特判
{
cout<<0;
return 0;
}
for(int i=1;i<=n;i++)
{
dp[fr[i]]=1;//i介绍fr[i]需要一步
q[fr[i]]=i;//fr[i]由i介绍
}
for(int s=0;s<=(1<<n)-1;s++)//枚举状态
{
if(dp[s]==inf) continue;//当前集合无法达到
for(int i=1;i<=n;i++)
{
if((s&(1<<i-1)))//满足s包含i
{
if(dp[s|fr[i]]>dp[s]+1)
{
dp[s|fr[i]]=dp[s]+1;//更新
q[s|fr[i]]=i;//存当前的介绍人
pre[s|fr[i]]=s;//存i介绍前的状态
}
}
}
}
cout<<dp[(1<<n)-1]<<endl;//输出步数
dfs((1<<n)-1);//输出介绍人
return 0;
}