poj 1419【図】最大独立セットテンプレート
1966 ワード
1つの無方向図では、白黒の2つの色を使用して頂点をシェーディングし、隣接する頂点が同時に黒にならないことを要求し、最大黒の頂点を染めることができる数と対応する頂点を求めます.
問題解決の考え方:
隣接する頂点間にエッジが接続され、モデルは無方向図の最大独立セットを求めるように変換されます.NP問題であるため,現在有効なアルゴリズムはない.
また最大グループ頂点数=補図の最大独立セット
そこで最適化Bron‐Kerboschを用いてその補図の最大団を求め,現在の図の最大独立セットを導くことができる.
http://poj.org/problem?id=1419
問題解決の考え方:
隣接する頂点間にエッジが接続され、モデルは無方向図の最大独立セットを求めるように変換されます.NP問題であるため,現在有効なアルゴリズムはない.
また最大グループ頂点数=補図の最大独立セット
そこで最適化Bron‐Kerboschを用いてその補図の最大団を求め,現在の図の最大独立セットを導くことができる.
http://poj.org/problem?id=1419
#include<cstdio>
#include<cstring>
#define N 1010
bool flag[N], a[N][N];
int ans, cnt[N], group[N], n, m, vis[N];
bool dfs( int u, int pos ){
int i, j;
for( i = u+1; i <= n; i++){
if( cnt[i]+pos <= ans ) return 0;
if( a[u][i] ){
// , Non-N(i)
for( j = 0; j < pos; j++ ) if( !a[i][ vis[j] ] ) break;
if( j == pos ){ // , i , i
vis[pos] = i;
if( dfs( i, pos+1 ) ) return 1;
}
}
}
if( pos > ans ){
for( i = 0; i < pos; i++ )
group[i] = vis[i]; //
ans = pos;
return 1;
}
return 0;
}
void maxclique()
{
ans=-1;
for(int i=n;i>0;i--)
{
vis[0]=i;
dfs(i,1);
cnt[i]=ans;
}
}
int main(){
int T;
scanf("%d",&T);
while( T-- ){
scanf("%d%d",&n,&m );
int x, y;
memset( a, 0, sizeof(a));
for(int i = 0; i < m; i++){
scanf("%d%d",&x,&y);
a[x][y] = a[y][x] = 1;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if( i == j ) a[i][j] = 0;
else a[i][j] ^= 1;
maxclique();
if( ans < 0 ) ans = 0;
printf("%d
", ans );
for(int i = 0; i < ans; i++)
printf( i == 0 ? "%d" : " %d", group[i] );
if( ans > 0 ) puts("");
}
}