根据题目中认识关系可以传递，利用并查集，把互相认识的人都放到一桌，最后有几个集合就是最少需要的桌数
代码：
#include<iostream> #include<cstdio> #include<memory.h> #include<stack> using namespace std; const int MAX=100005; int fa[MAX],rank[MAX],vis[MAX]; int n,m; void init() { for(int i=1;i<=100000;i++) { fa[i]=i; rank[i]=0; } } int find(int x) { if(x!=fa[x]) fa[x]=find(fa[x]); return fa[x]; } bool Union(int x,int y) { int a=find(x),b=find(y); //cout<<x<<" "<<a<<" "<<y<<" "<<b<<endl; if(a==b) return false; if(rank[a]>rank[b]) fa[b]=a; else { fa[a]=b; if(rank[a]==rank[b]) rank[b]++; } return true; } int main() { int i,j,flag; while(scanf("%d%d",&i,&j)) { if(i==-1&&j==-1) break; if(i==0&&j==0) { puts("Yes"); continue; } init(); memset(vis,0,sizeof(vis)); flag=0; Union(i,j);//不要忘了 vis[i]=vis[j]=1; while(true) { scanf("%d%d",&i,&j); if(i==0&&j==0) break; if(!Union(i,j)) flag=1; vis[i]=vis[j]=1; } int cnt=0; for(i=1;i<=100000;i++) if(vis[i]&&fa[i]==i) cnt++; if(cnt>1) flag=1; if(flag) puts("No"); else puts("Yes"); } return 0; }
