再复习再总结再提高~~
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#define not !
#define and &&
#define or ||
#define ri register int
#define rep(inc, frm, to) for (ri inc = frm; inc < (to); ++inc)
#define rep2(inc, frm, to) for (ri inc = frm; inc > (to); --inc)
#define setbit(x, y) x |= 1 << y
#define clrbit(x, y) x &= ~(1 << y)
#define getbit(x, y) x >> y & 1
#define flipbit(x, y) x ^= 1 << y
#define show_bin(x) { rep2(i, 31, ~0) printf("%d%c", getbit(x, i), i ? 0 : 10); }
typedef long long int ll;
#define r() fast_read()
bool is_digit(const char c) {
return c >= 48 and c <= 57;
}
ll fast_read(void) {
ll n = 0, sign = 1;
char c = getchar();
while (not is_digit(c)) {
if (c == '-') sign = ~0;
c = getchar();
}
while (is_digit(c)) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
#define MAX_N 110
int head[MAX_N], edge_cnt;
typedef struct Edge Edge;
struct Edge {
int to, nxt;
} edges[MAX_N];
void addEdge(int u, int v) {
*(edges + ++edge_cnt) = (Edge) {.to = v, .nxt = *(head + u)};
*(head + u) = edge_cnt;
}
void print_graph(const int n) {
rep(u, 1, n + 1) {
printf("Vertex: %d -->", u);
for (int e = *(head + u); e; e = (edges + e)->nxt)
printf("[%d]\t", (edges + e)->to);
putchar(10);
}
}
int n, m;
typedef struct NodePair DqElemType;
typedef struct NodePair {
int node;
int depth;
} Pair;
/* ======================================================================================================== */
#include <string.h>
#include <errno.h>
// typedef int DqElemType;
/* 双向循环链表的存储结构 */
typedef struct DuLNode {
DqElemType data; /* 数据域 */
struct DuLNode* prior; /* 指向直接前驱结点的指针 */
struct DuLNode* next; /* 指向直接后继结点的指针 */
} DuLNode, *PtrToNode;
/* Double-ended Queue */
typedef struct {
PtrToNode head; /* 指向头结点的指针 */
size_t length; /* 双端队列中元素的个数 */
} Deque;
/* ======================== Deque API ===================== */
bool InitDeque(Deque* Q);
bool DequeEmpty(Deque* Q);
size_t DequeLength(Deque* Q);
DqElemType GetFront(Deque* Q);
DqElemType GetBack(Deque* Q);
DqElemType GetRear(Deque* Q);
void PushFront(Deque* Q, DqElemType e);
void PushBack(Deque* Q, DqElemType e);
void PopFront(Deque* Q);
void PopBack(Deque* Q);
void DestroyDeque(Deque* Q);
/* ======================== Deque API ===================== */
bool InitDeque(Deque* Q) {
Q->head = malloc(sizeof *Q->head);
if (!Q->head) {
fprintf(stderr, "%s\n", strerror(errno));
return false;
}
Q->head->prior = Q->head->next = Q->head; // importance! importance! importance!
Q->length = 0;
return true;
}
bool DequeEmpty(Deque* Q) {
return Q->head->next == Q->head;
}
size_t DequeLength(Deque* Q) {
return Q->length;
}
DqElemType GetFront(Deque* Q) {
if (DequeEmpty(Q)) {
fprintf(stderr, "%s\n", "The deque is empty!");
return (DqElemType) {-1, -1};
}
return Q->head->next->data;
}
DqElemType GetBack(Deque* Q) {
return GetRear(Q);
}
DqElemType GetRear(Deque* Q) {
if (DequeEmpty(Q)) {
fprintf(stderr, "%s\n", "The deque is empty!");
return (DqElemType) {-1, -1};
}
return Q->head->prior->data;
}
void PushFront(Deque*Q, DqElemType e) {
PtrToNode s;
s = malloc(sizeof *s);
s->data = e;
s->prior = Q->head;
s->next = Q->head->next;
Q->head->next = Q->head->next->prior = s;
++Q->length;
}
void PushBack(Deque* Q, DqElemType e) {
PtrToNode s;
s = malloc(sizeof *s);
s->data = e;
s->prior = Q->head->prior;
s->next = Q->head;
Q->head->prior = Q->head->prior->next = s;
++Q->length;
}
void PopFront(Deque* Q) {
if (DequeEmpty(Q)) return;
PtrToNode p = Q->head->next;
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
--Q->length;
}
void PopBack(Deque* Q) {
if (DequeEmpty(Q)) return;
PtrToNode p = Q->head->prior;
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
--Q->length;
}
void DestroyDeque(Deque* Q) {
if (DequeEmpty(Q)) return;
PtrToNode head = Q->head, p = head->next, nxt;
while (p->next != head) {
nxt = p->next;
free(p);
p = nxt;
}
free(head);
Q->length = 0;
}
/* ======================================================================================================== */
void tour(void) { // tour == traverse
Deque Q;
InitDeque(&Q);
PushBack(&Q, (Pair) {.node = 1, .depth = 0});
int cnts[MAX_N] = { 0 },
max_depth = 0,
node,
depth;
while (not DequeEmpty(&Q)) {
// node = GetFront(&Q).node, depth = GetFront(&Q).depth; PopFront(&Q); // BFS
node = GetBack(&Q).node, depth = GetBack(&Q).depth; PopBack(&Q); // DFS
max_depth = fmax(max_depth, depth);
cnts[depth] += not(head[node]);
for (int e = head[node]; e; e = edges[e].nxt)
PushBack(&Q, (Pair) {.node = edges[e].to, .depth = depth + 1});
}
rep(i, 0, max_depth + 1) printf("%d ", cnts[i]);
DestroyDeque(&Q);
}
signed main(int argc, char const *argv[]) {
// freopen("test.in", "r", stdin);
n = r(), m = r();
for (int pid, k; m--;) {
pid = r(), k = r();
while (k--) addEdge(pid, r());
}
tour();
// fclose(stdin);
return ~~(0 ^ 0);
}
BFS
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, k, parent, child;
int main(void) {
cin >> n >> m;
// build the directed graph (家谱树)
vector<vector<int>> graph(n + 1);
while (m--) {
cin >> parent >> k;
for (int i = 0; i < k; ++i) {
cin >> child;
graph[parent].emplace_back(child);
}
}
queue<int> q{{1}};
while (not q.empty()) {
size_t sz = q.size();
int leaves = 0;
while (sz--) {
auto cur = q.front(); q.pop();
leaves += graph[cur].empty();
for (const auto& child : graph[cur])
q.emplace(child);
}
printf("%d ", leaves);
}
}
复习总结提高版
#include <iostream>
#define f(inc, frm, to) for (unsigned inc = frm; inc < to; ++inc)
using namespace std;
const int N = 110;
int head[N], edge_cnt;
struct Edge {
int to, nxt;
} edges[N * N];
inline void addEdge(int u, int v) {
edges[++edge_cnt] = {v, head[u]};
head[u] = edge_cnt;
}
int n, m;
inline void print_graph(void) {
putchar(10);
f(u, 1, n + 1) {
printf("vertex %d: [", u);
for (int e = head[u]; e; e = edges[e].nxt)
printf(" %d", edges[e].to);
puts(" ]");
}
}
inline void BFS(void) {
int q[N] = {1}, front = 0, rear = 1, cnt;
while (front < rear) {
cnt = 0;
size_t s = rear - front;
while (s--) {
const int curr = q[front++];
if (not head[curr]) { ++cnt; continue; }
for (int e = head[curr]; e; e = edges[e].nxt)
q[rear++] = edges[e].to;
}
printf("%d ", cnt);
}
}
signed main(int argc, char const *argv[]) {
scanf("%d%d", &n, &m);
int id, k, x;
while (m--) {
scanf("%d%d", &id, &k);
while (k--) {
scanf("%d", &x);
addEdge(id, x);
}
}
// print_graph();
BFS();
return ~~(0 ^ 0);
}