清华数据结构PA7——无线广播(Broadcast)

题目：https://dsa.cs.tsinghua.edu.cn/oj/problem.shtml?id=1148

思路很简单，选取一个无前驱的点，给定一个fm然后进行bfs，将其相邻的点给定一个与其相异的fm，依此类推，当出现一个点已有fm的情况下要赋予一个不同的fm的情况时，此时就是无法满足要求的。

#include
#define MAXSIZE 10000
#define max(a,b) a>b?a:b
using namespace std;struct edge
{int adjvex = 0;edge* next;
};struct vertex
{int fm = 0;edge* firstedge = NULL;
};int rear = 0;
int top = 0;
int n, m, i, j;
edge* temp = NULL;
int queue[MAXSIZE];
vertex adjlist[MAXSIZE];int bfs()
{adjlist[0].fm = 104;queue[++top] = 0;while (top!=rear){int key = queue[top--];for (edge* e = adjlist[key].firstedge; e; e = e->next){int x = e->adjvex;if (adjlist[x].fm != adjlist[key].fm){if (adjlist[key].fm == 104){if (adjlist[x].fm == 0){queue[++top] = x;}adjlist[x].fm = 98;}else{if (adjlist[x].fm == 0){queue[++top] = x;}adjlist[x].fm = 104;}}else{return -1;}}}return 1;
}int main()
{scanf("%d%d", &n, &m);for (int k = 0; k < m; k++){scanf("%d%d", &i, &j);i--; j--;temp = new edge;temp->adjvex = j;temp->next = adjlist[i].firstedge;adjlist[i].firstedge = temp;temp = new edge;temp->adjvex = i;temp->next = adjlist[j].firstedge;adjlist[j].firstedge = temp;}int result = bfs();printf("%d", result);
}