题意补图上求每个节点从source的深度，到达不了就深度为-1，依次输出。就是个补图bfs...............mdzz
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <set> using namespace std; const int MAXE = 200005; struct Edge { int from, to; int next; }edge[MAXE]; struct Node { int v; int step; }tmp; int cnt; int head[200005]; int d[200005]; int n, m; int source; set<int>::iterator it; void addedge(int u, int v) { edge[cnt].next = head[u]; edge[cnt].from = u; edge[cnt].to = v; head[u] = cnt++; edge[cnt].next = head[v]; edge[cnt].from = v; edge[cnt].to = u; head[v] = cnt++; } void bfs(int s) { Node u; int v; set<int> a; set<int> b; queue<Node> q; tmp.v = s; tmp.step = 0; q.push(tmp); for (int i = 1; i <= n; i++) { if (i == s) continue; a.insert(i); } while (!q.empty()) { u = q.front(); q.pop(); for (int i = head[u.v]; i != -1; i = edge[i].next) { v = edge[i].to; if (a.count(v)) { a.erase(v); b.insert(v); } } for (it = a.begin(); it != a.end(); it++) { tmp.v = *it; tmp.step = u.step + 1; d[*it] = tmp.step; q.push(tmp); } a.swap(b); b.clear(); } } int main(void) { int T; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); cnt = 0; memset(head, -1, sizeof head); memset(d, -1, sizeof d); int l, r; for (int i = 0; i < m; i++) { scanf("%d%d", &l, &r); addedge(l, r); } scanf("%d", &source); int flag = 1; bfs(source); if (source != 1) { printf("%d", d[1]); flag = 0; } for (int i = 2; i <= n; i++) { if (source == i) continue; if (flag == 0) printf(" "); printf("%d", d[i]); flag = 0; } printf("\n"); } return 0; }
