1455.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1455 on 2005-11-06 at 19:20:01 */ 
#include <cstdio>
#include <cstring>

const int MAX = 32;

bool edge[MAX][MAX];
int n, m;
bool visit[MAX][MAX];

int DFS(int, int);

int main()
{
	int i, max, p;
	int x, y;
	
	while(scanf("%d %d", &n, &m) == 2) {
		if(n == 0 && m == 0) {
			return 0;
		} else {
			memset(edge, false, sizeof(edge));
			for(i = 0; i < m; i++) {
				scanf("%d %d", &x, &y);
				edge[x][y] = edge[y][x] = true;
			}
			max = 0;
			for(i = 0; i < n; i++) {
				memset(visit, false, sizeof(visit));
				p = DFS(i, 0);
				if(max < p) {
					max = p;
				}
				if(max == m) {
					break;
				}
			}
			printf("%d\n", max);
		}
	}
	
	return 0;
}

int DFS(int src, int d)
{
	int stack[MAX], top = 0;
	int i, max = d;
	for(i = 0; i < n; i++) {
		if(edge[src][i] && !visit[src][i]) {
			stack[top++] = i;
		}
	}
	for(i = 0; i < top; i++) {
		visit[src][stack[i]] = visit[stack[i]][src] = true;
		int p = DFS(stack[i], d+1);
		if(max < p) {
			max = p;
		}
		visit[src][stack[i]] = visit[stack[i]][src] = false;
	}
	return max;
}