1115.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1115 on 2005-10-07 at 16:52:07 */ 
#include <cstdio>
#include <cstring>
#define  MAX  32

int main()
{
	bool chan[MAX][MAX], together;
	int i, j, stack[MAX], top, channel[MAX], repN, t;
	int n, chanN, chanStatus[MAX];
	char repeater, neighbor[MAX];
	
	while(scanf("%d", &n) == 1) {
		if(n == 0) {
			return 0;
		} else {
			while(getchar() != '\n')
				;
			memset(chan, true, sizeof(chan));
			for(i = 0; i < n; i++) {
				repeater = getchar();
				getchar();
				gets(neighbor);
				for(j = 0; neighbor[j] != '\0'; j++) {
					chan[repeater-'A'][neighbor[j]-'A'] = false;
					chan[neighbor[j]-'A'][repeater-'A'] = false;
				}
			}
			chanN = 0;
			memset(chanStatus, 0, sizeof(chanStatus));
			top = 0;
			for(i = 0; i < n; i++) {
				if(chanStatus[i] == 0) {
					repN = 0;
					channel[repN++] = i;
					stack[top++] = i;
					chanStatus[i] = 1;
					while(top != 0) {
						t = stack[--top];
						together = true;
						for(j = 0; j < repN; j++) {
							if(!chan[t][channel[j]]) {
								chanStatus[t] = 2;
								together = false;
								break;
							}
						}
						if(together) {
							channel[repN++] = t;
							for(j = 0; j < n; j++) {
								if(chan[t][j] && (chanStatus[j] == 0)) {
									stack[top++] = j;
									chanStatus[j] = 1;
								}
							}
						}
					}
					for(j = 0; j < n; j++) {
						if(chanStatus[j] == 2) {
							chanStatus[j] = 0;
						}
					}
					chanN++;
				}
			}
			if(chanN == 1) {
				printf("1 channel needed.\n");
			} else {
				printf("%d channels needed.\n", chanN);
			}
		}
	}
	
	return 0;
}