知識點
模版——鏈表的前插法
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;
}
)
