首页 > 代码库 > Maximum Clique
Maximum Clique
Maximum Clique |
| Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
| Total Submission(s): 92 Accepted Submission(s): 60 |
Problem Description Given a graph G(V, E), a clique is a sub-graph g(v, e), so that for all vertex pairs v1, v2 in v, there exists an edge (v1, v2) in e. Maximum clique is the clique that has maximum number of vertex. |
Input Input contains multiple tests. For each test: The first line has one integer n, the number of vertex. (1 < n <= 50) The following n lines has n 0 or 1 each, indicating whether an edge exists between i (line number) and j (column number). A test with n = 0 signals the end of input. This test should not be processed. |
Output One number for each test, the number of vertex in maximum clique. |
Sample Input 50 1 1 0 11 0 1 1 11 1 0 1 10 1 1 0 11 1 1 1 00 |
Sample Output 4 |
Author CHENG, Long |
Source ZOJ Monthly, February 2003 |
Recommend mcqsmall |
/*题意：就是给你一个图，然后输出最大团嘛*/#include<bits/stdc++.h>using namespace std;/***********************************最大团模板************************************/struct MAX_CLIQUE { static const int N=60; bool G[N][N]; int n, Max[N], Alt[N][N], ans; bool DFS(int cur, int tot) { if(cur==0) { if(tot>ans) { ans=tot; return 1; } return 0; } for(int i=0; i<cur; i++) { if(cur-i+tot<=ans) return 0; int u=Alt[tot][i]; if(Max[u]+tot<=ans) return 0; int nxt=0; for(int j=i+1; j<cur; j++) if(G[u][Alt[tot][j]]) Alt[tot+1][nxt++]=Alt[tot][j]; if(DFS(nxt, tot+1)) return 1; } return 0; } int MaxClique() { ans=0, memset(Max, 0, sizeof Max); for(int i=n-1; i>=0; i--) { int cur=0; for(int j=i+1; j<n; j++) if(G[i][j]) Alt[1][cur++]=j; DFS(cur, 1); Max[i]=ans; } return ans; }};MAX_CLIQUE fuck;/***********************************最大团模板************************************/int n;int main(){ // freopen("in.txt","r",stdin); while(scanf("%d",&fuck.n)!=EOF&&fuck.n){ for(int i=0;i<fuck.n;i++){ for(int j=0;j<fuck.n;j++){ scanf("%d",&fuck.G[i][j]); } } printf("%d\n",fuck.MaxClique()); } return 0;}
Maximum Clique
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。