A summit (峰会) is a meeting of heads of state or government. Arranging the rest areas for the summit is not a simple job. The ideal arrangement of one area is to invite those heads so that everyone is a direct friend of everyone.
Now given a set of tentative arrangements, your job is to tell the organizers whether or not each area is all set.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N (≤ 200), the number of heads in the summit, and M, the number of friendship relations. Then M lines follow, each gives a pair of indices of the heads who are friends to each other. The heads are indexed from 1 to N.
Then there is another positive integer K (≤ 100), and K lines of tentative arrangement of rest areas follow, each first gives a positive number L (≤ N), then followed by a sequence of L distinct indices of the heads. All the numbers in a line are separated by a space.
Output Specification:
For each of the K areas, print in a line your advice in the following format:
if in this area everyone is a direct friend of everyone, and no friend is missing (that is, no one else is a direct friend of everyone in this area), print
Area X is OK.
.if in this area everyone is a direct friend of everyone, yet there are some other heads who may also be invited without breaking the ideal arrangement, print
Area X may invite more people, such as H.
whereH
is the smallest index of the head who may be invited.if in this area the arrangement is not an ideal one, then print
Area X needs help.
so the host can provide some special service to help the heads get to know each other.
Here X
is the index of an area, starting from 1 to K
.
Sample Input:
8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
2 4 6
3 3 2 1
Sample Output:
Area 1 is OK.
Area 2 is OK.
Area 3 is OK.
Area 4 is OK.
Area 5 may invite more people, such as 3.
Area 6 needs help.
题意:
给N个点,M条边。K个询问。每个询问给出L个点,问这L个点是不是两两相连的。
如果两两相连:
存不存在一个其它的点,与这L个点都有连接:
有:Area i may invite more people, such as 这个点.
没有:Area i is OK.
不是两两相连:Area i needs help.
题解:
AC代码:
#include<bits/stdc++.h> using namespace std; int e[205][205]; int a[205]; int v[205]; int n,m; int main(){ cin>>n>>m; memset(e,0,sizeof(e)); for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; e[u][v]=e[v][u]=1;//邻接矩阵存储 } int k; cin>>k; int num; for(int i=1;i<=k;i++){//k个询问 cin>>num; memset(v,0,sizeof(v));//v来标记所询问的num个点 for(int j=1;j<=num;j++) { cin>>a[j]; v[a[j]]=1;//做上标记 } int f=1;//是不是两两相连 for(int j=1;j<=num;j++){ for(int p=j+1;p<=num;p++){ if(e[a[j]][a[p]]!=1) f=0; break; } } if(!f) cout<<"Area "<<i<<" needs help."; else{//如果是两两相连 int ans=-1;//是否存在 for(int j=1;j<=n;j++){//查询存不存在一个点与这num个点都相连 if(v[j]) continue;//本身是num个点里的不算 int ff=1; for(int p=1;p<=num;p++){ if(e[a[p]][j]!=1){ ff=0; break; } } if(ff) {//满足与num中的每个点都相连 ans=j;//存在 break; } } if(ans!=-1){//存在 cout<<"Area "<<i<<" may invite more people, such as "<<ans<<"."; }else{//不存在 cout<<"Area "<<i<<" is OK."; } } if(i!=k) cout<<endl;//行末无空行 } return 0; }