题意:
最多能选取多少点,没有边相连。
解法:
取反图,求最大团
代码:
#include#include #include using namespace std;const int maxn=11000;int e,ans,res,n,m,head[110],nxt[maxn],pnt[maxn],color[110],ansa[110];bool vis[110];void AddEdge(int u,int v){ nxt[e]=head[u];pnt[e]=v;head[u]=e++; nxt[e]=head[v];pnt[e]=u;head[v]=e++;}void DFS(int u,int cnt){ if(u==n+1) { if(cnt>ans) { ans=cnt; memcpy(ansa,color,sizeof(color)); } return; } bool can=true; for(int i=head[u];i!=-1;i=nxt[i]) if(color[pnt[i]]) { can=false; break; } if(can) { color[u]=1; DFS(u+1,cnt+1); color[u]=0; } if(cnt+n-u>ans) DFS(u+1,cnt);}int main(){ int T; scanf("%d",&T); while(T--) { ans=e=0; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); for(int i=0;i