题意:判断某图(不一定是简单图)是否为二分图。 难度:3星。
一开始做的时候没有意识到这是二分图的问题,考虑不周全,做错了。想的是:任意两个点(怪)的连接集(矛盾集)之间没有交集,则可推断出肯定结果。这并不是判定二分图的充分条件。
后来搜索发现,应该用广度优先搜索算法(BFS)来判定题图是否二分图。果然去年学的数据结构记不清了,得再温习一下BFS。其他的知识想必也需要温习了!
思路:用广度优先遍历每个节点,为其着色。若碰到相邻节点间的颜色相同,则说明题图非二分图。需要注意题图为非连通图的情况,须在BFS外套一个循环。
题解代码:
/* * Bad Horse - Practice Round China New Grad Test 2014 * * * 原错误思路:任意两个点(怪)的连接集(矛盾集)之间没有交集, * 则可以分为两个没有内部连接的子集;——(这不就是偶图嘛) * 题目应等价为:判断某图是否二分图; * * 用广度优先搜索算法(BFS)解决: * 1、建立邻接表: * 从文件读取数据,建立nameList[][]、邻接表troubleNo[][]; * 2、根据邻接表用广度优先搜索算法为每个节点着色: * 1)初始化,将节点0(nameList[0][])着色为‘1’(即,color[0]=1); * 2)建立一个先进先出的队列queue[],将节点0加入队列; 3)取出头节点(节点0),将其相邻节点加入队列,并将相邻节点着异色(即,color[i]=1-color[0]); * 如果邻节点已着色,且与现节点的颜色相同,则说明题图非二分图,break; * 4)循环取出队列头节点,用类似3)的方法处理,直至处理完此连通图中全部节点; * 3、为处理题图为非连通图(由多个简单图组成)的情况,须在外层再套一个循环; * */ #include <iostream> #include <fstream> using namespace std; #define MAX_NAME_LENGTH 32 #define MAX_NAME_NUMBER 200 int makeNameList(char name[]); char nameList[MAX_NAME_NUMBER][MAX_NAME_LENGTH]; int troubleNo[MAX_NAME_NUMBER][MAX_NAME_NUMBER], nameCnt; int color[MAX_NAME_NUMBER]; int queue[MAX_NAME_NUMBER], head, tail; int main() { ifstream inputFile; ofstream outputFile; int T, M; char nameA[MAX_NAME_LENGTH], nameB[MAX_NAME_LENGTH]; int nameANo, nameBNo; int canSplit; int i, j, caseNo; inputFile.open("E:\\C++\\GCJ\\China New Grad Test 2014\\Practice Round\\Bad Horse\\A-small-practice-2.in"); outputFile.open("E:\\C++\\GCJ\\China New Grad Test 2014\\Practice Round\\Bad Horse\\A-small-practice-2.out"); inputFile >> T; for (caseNo = 1; caseNo <= T; caseNo++) { inputFile >> M; for (i = 0; i < 2 * M; i++) { /* troubleNo[i][0]存储的是与nameList[i][]邻接的节点个数 */ troubleNo[i][0] = 0; } for (i = 0, nameCnt = 0; i < M; i++) { inputFile >> nameA >> nameB; cout << nameA << ' ' << nameB << endl; /* 输入nameA、nameB,返回值为各自序号 */ nameANo = makeNameList(nameA); nameBNo = makeNameList(nameB); /* 建立邻接表 */ troubleNo[nameANo][++troubleNo[nameANo][0]] = nameBNo; troubleNo[nameBNo][++troubleNo[nameBNo][0]] = nameANo; }//for (i = 0, nameCnt = 0; i < M; i++) canSplit = 1; memset(color, 0, sizeof(int) * MAX_NAME_NUMBER); while (1) { /* BFS */ /* 找到未访问的节点(color[j]==0) */ for (j = 0; color[j] && j < nameCnt; j++); if (j == nameCnt) { break; } head = tail = 0; queue[tail++] = j; color[j] = 1; while (head < tail) { /* 队列不为空 */ int tmp = queue[head++]; /* 取出头节点 */ for (j = 1; j <= troubleNo[tmp][0]; j++) { /* troubleNo[j][0]存储的是与nameList[j][]邻接的节点个数 */ if (!color[troubleNo[tmp][j]]) { /* 若邻接点未着色,将其着与现节点不同的颜色,并将其加入队列 */ queue[tail++] = troubleNo[tmp][j]; color[troubleNo[tmp][j]] = 0 - color[tmp]; } else if (color[troubleNo[tmp][j]] == color[tmp]) { /* 若邻接点与现节点颜色相同,说明原图非二分图,break */ canSplit = 0; goto nextCase; } }//for (j = 1; j <= troubleNo[tmp][troubleNo[tmp][0]]; j++) }//while (head < tail) }//while (1) nextCase: if (!canSplit) { cout << caseNo << " No\n"; outputFile << "Case #" << caseNo << ": No\n"; } else { cout << caseNo << " Yes\n"; outputFile << "Case #" << caseNo << ": Yes\n"; } }//for (caseNo = 1; caseNo <= T; caseNo++) inputFile.close(); outputFile.close(); system("pause"); return 0; } int makeNameList(char name[]) { /* 输入name */ /* 返回name的序号 */ int i, existFlag; for (i = 0, existFlag = 0; i < nameCnt; i++) { if (!strcmp(nameList[i], name)) { existFlag = 1; break; } } if (!existFlag) { strcpy(nameList[nameCnt++], name); } return i; }