UVA 10004   Bicoloring 

#include 
#include int n, m;
int lu[205][205];
int num[205];
int visd[205];
int vis[205][205];
int a, b;
int judge;
void dfs(int n, int nu)
{for (int i = 0; i < num[n]; i ++){if (vis[n][lu[n][i]] == 0){if (visd[lu[n][i]] == 1){if (nu % 2){judge = 1;return;}return;}visd[lu[n][i]] = 1;vis[n][lu[n][i]] = vis[lu[n][i]][n] = 1;dfs(lu[n][i], nu + 1);visd[lu[n][i]] = 0;vis[n][lu[n][i]] = vis[lu[n][i]][n] = 0;}}
}
int main()
{while (scanf("%d", &n) != EOF && n){judge = 0;memset(lu, 0, sizeof(lu));memset(num, 0, sizeof(num));scanf("%d", &m);for (int i = 0; i < m; i ++){scanf("%d%d", &a, &b);lu[a][num[a]]  = b;lu[b][num[b]] = a;num[a] ++;num[b] ++;}for (int i = 0; i < n; i ++){memset(visd, 0, sizeof(visd));memset(vis, 0, sizeof(vis));visd[i] = 1;dfs (i, 1);if (judge){printf("NOT BICOLORABLE.\n");break;}}if (!judge)printf("BICOLORABLE.\n");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！