计算机算法分析与设计5-20部落卫队问题C++代码回溯法解最大团

计算机算法分析与设计5-20部落卫队问题C++代码。

//化成经典最大团问题


#include

int map[100][100];

int n;

int x[100]  bestx[100]  cn  bestn;

void backtrack（int i）{
    if（i > n）{
		for（int j = 1 ; j <= n ; j ++）{
			bestx[j] = x[j];
		}
		bestn = cn;
		return;
    }
    int OK = 1;
    for（int j = 1 ; j < i ; j ++）{
		if（x[j] && map[i][j] == 0）{
			OK = 0 ;
			break;
		}
    }
    if（OK）{
		x[i] = 1;
		cn ++;
		backtrack（i + 1）;
		x[i] = 0;
		cn --;
    }

    if（cn + n - i > bestn）{
		x[i] = 0;
		backtrack（i + 1）;
    }
}

int main（）{

    int m;

    while（~scanf（“%d%d“  &n  &m））{
    	int a  b;
    	for（int i = 1 ; i <= n ; i ++）{
			for（int j = 1 ; j <= n ; j ++）{
				map[i][j] = 1;
			}
    	}
		for（int i = 1 ; i <= m ; i ++）{
			scanf（“%d%d“  &a  &b）;
			map[a][b] = 0;
			map[b][a] = 0;
		}
		backtrack（1）;
		printf（“%d\n“  bestn）;
		for（int i = 1 ; i <= n ; i ++）{
			printf（“%d “  bestx[i]）;
		}
		printf（“\n“）;
    }

    return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件         938  2013-05-26 07:54  部落卫队问题.cpp