知识点
模版——链表的前插法
head表示头结点的下标
ver[i]表示结点i 的值
tot存储当前已经用到了哪个
add用于将x插到头结点
int head=1;
intt ver[N],Next[N];
int ttot=-1;
void add(int x){ver[++tot]=x;Next[tot]=head;head=tot;
}常见的链式前向星三种实现形式：
1、结构体形式的实现
通过结构体记录每条边的信息
定义一个结构体
其中 to 表示指向的点，next 表示下一个节点存储的下标，c 表示权值
struct edge{int to,next,c;
}e[N];
int cnt=0;
void add(int u,int v,int c){cnt++;e[cnt].to=v;e[cnt].c=c;e[cnt].next=head[u];head[u]=cnt;
}使用之前将head数组清空为-1
2、数组模拟实现
通过多个数组记录每条边的信息。
head[u]即表示节点 u 对应的边表的头节点
e[]记录这条边指向的点
w[]记录边的权值
ne[]记录下一个点的位置
加边函数的写法：
void add(int a,int b,int c){e[idx]=b;//idx记录边的编号 w[idx]=c;//e[idx]=b，w[idx]=c用来记录边的信息 ne[idx]=head[a];//-用来添加一条边 head[a]=idx++;// /
}使用之前将head数组清空为-1
3、vector 实现
使用 vector 嵌套 vector
最外层 vector 需要指定大小，方便加边。
定义：vector<vector<int>> a(100);
加边：e[a].push_back(b);
练习
读入一个有 n 个节点，m 条边的有向图
struct node {int to, next;
} edge[1000];
int head[N],cnt = 0;
int n, m;
void add(int a, int b) {edge[++cnt].to = b;edge[cnt].next = head[a], head[a] = cnt;
}
int main() {memset(head， -1，sizeof head); cin >> n >> m;for (int i = 0; i< m; i++) {int a, b;cin >> a >> b; add(a, b);}return 0;
}int head[N],e[N],ne[N],idx = 0;
void add(int a, int b) {e[idx] = b， ne[idx] = head[a], head[a] = idx++;
}
int n, m;
int main() {memset(head，-1, sizeof head); cin >> n >> m;for (int i = 0; i< m; i++) {int a, b;cin >> a >> b; add(a， b);}return 0;
}vector<vector<int>> q(1000);
int n, m;
int main() {cin >> n >> m;for (int i = 1; i<= m; i++) {int a, b;cin >> a >> b;q[a].push_back(b);}return 0;
}
)
