链式前向星

//链式前向星 类似于邻接表, 不同点 1.用下标代替指针 2.向前插入 const int MAXSIZE = 1e6 + 7; struct Tail { int to, next; }tail[MAXSIZE]; int head[MAXSIZE] = {0}, tot = 0; bool visit[MAXSIZE] = {0}; //head数组 相当于 尾巴节点的头指针(第一个) //tail 是尾巴节点 next 指向 下一个尾巴 节点下标 void Add(int _head, int _tail) { //++tot 相当于 创建一个新节点, .to 记录尾巴节点 tail[++tot].to = _tail; //head[_head] 相当于 邻接表里面的头指针 , 将新节点的 next 指向 头指针 tail[tot].next = head[_head]; //将头指针指向 新节点 head[_head] = tot; } int main() { int n,m,start,over; while (cin >> n >>m) { tot = 0; memset(head, 0, sizeof(head)); memset(tail, 0, sizeof(tail)); memset(visit, 0, sizeof(visit)); for (int i = 0; i < m; ++i) { cin >> start >> over; Add(start, over); } for (int i = 1; i <= n; i++)//n个起点 { if(visit[i]) continue; visit[i] = true; cout << i <<" "; for (int j = head[i]; j; j = tail[j].next)//遍历以i为起点的边 { if(visit[tail[j].to]) continue; visit[tail[j].to] = true; cout << tail[j].to << " "; } } cout << endl; } return 0; }