圖

對于一張圖而言，我們定義圖是一種由邊和點構成的的一個玩意（其實是嚴謹定義我記不住了QWQ，但是不影響學習）

一般來說，圖的存儲難度主要在記錄邊的信息
無向圖的存儲中，只需要將一條無向邊拆成兩條即可
鄰接矩陣：用一個二維數組 edg[N][N] 表示
edg[i][j] 就對應由 i 到 j 的邊信息
edg[i][j] 可以記錄 Bool，也可以記錄邊權
缺點：如果有重邊有時候不好處理
空間復雜度 O(V^2)

點度等額外信息也是很好維護的

#include <bits/stdc++.h>using namespace std;const int N = 5005;int ideg[N], odeg[N], n, m, edg[N][N];
bool visited[N];void travel(int u, int distance)
{cout << u << " " << distance << endl; visited[u] = true;for (int v = 1; v <= n; v++)if (edg[u][v] != -1 && !visited[v])//是否已經訪問過 travel(v, distance + edg[u][v]); //if there is an edge (u, v) and v has not been visited, then travel(v)
}
int main()
{cin >> n >> m;memset(edg, -1, sizeof edg);memset(visited, false, sizeof visited);for (int u, v, w, i = 1; i <= m; i++)cin >> u >> v >> w, edg[u][v] = w, odeg[u]++, ideg[v]++;//出度和入度 for (int i = 1; i <= n; i++)cout << ideg[i] << " " << odeg[i] << endl;for (int i = 1; i <= n; i++)if (!visited[i]) travel(i, 0);
}/*
Given a graph with N nodes and M unidirectional edges.
Each edge e_i starts from u_i to v_i and weights w_i
Output a travelsal from node 1 and output degree of each node.
*/

其實這個英文注釋也還蠻不錯的啊

鄰接矩陣本質上其實就是一個二維數組，它在存儲一個稠密圖的時候效率比較好，但是稀松圖的話就非常浪費空間

所以我們就沒有必要用二維數組記錄信息，我們只需要對每一個點記錄他的出邊就行

這樣記的話，復雜度就是他的邊數

對每一個點 u 記錄一個 List[u]，包含所有從 u 出發的邊
直接用數組實現 List[u]？讀入邊之前不知道 List[u] 長度
手寫鏈表（鏈式前向星）
用 STL 中的 vector 實現變長數組，當然你想要手寫指針也沒問題
只需要 O(V + E) 的空間就能實現圖的存儲（邊數加點數）

其實寫這個鏈表存儲0有很多方式啊，你可以用指針，手寫指針，也可以用vector ，還可以用數組毛模擬

我們詳細理解一下代碼

#include <bits/stdc++.h>using namespace std;const int N = 5005;struct edge {int u, v, w; edge *next;//next指針指向 edge(int _u, int _v, int _w, edge *_next):u(_u), v(_v), w(_w), next(_next) {}
};
edge *head[N]; //List[u] 最前面的節點是誰 
int ideg[N], odeg[N], n, m;
bool visited[N];void add(int u, int v, int w)
{edge *e = new edge(u, v, w, head[u]);head[u] = e;
}
void travel(int u, int distance)
{cout << u << " " << distance << endl; visited[u] = true;for (edge *e = head[u]; e ; e = e -> next)if (!visited[e -> v])travel(e -> v, distance + e -> w); //if there is an edge (u, v) and v has not been visited, then travel(v)
}
int main()
{cin >> n >> m;memset(visited, false, sizeof visited);memset(head, 0, sizeof head);for (int u, v, w, i = 1; i <= m; i++)cin >> u >> v >> w, add(u, v, w), odeg[u]++, ideg[v]++;for (int i = 1; i <= n; i++)cout << ideg[i] << " " << odeg[i] << endl;for (int i = 1; i <= n; i++)if (!visited[i]) travel(i, 0);
}/*
Given a graph with N nodes and M unidirectional edges.
Each edge e_i starts from u_i to v_i and weights w_i
Output a travelsal from node 1 and output degree of each node.
*/

但是我個人是不用指針的，因為可能還是不習慣的原因吧，而且指針的寫法并沒有什么特別的優點

還有一個數組模擬版本

#include <bits/stdc++.h>using namespace std;const int N = 5005;struct edge {int u, v, w, next;
}edg[N];
int head[N]; //List[u] stores all edges start from u
int ideg[N], odeg[N], n, m, cnt; //cnt: numbers of edges
bool visited[N];void add(int u, int v, int w)
{int e = ++cnt;edg[e] = (edge){u, v, w, head[u]};head[u] = e;
}
void travel(int u, int distance)
{cout << u << " " << distance << endl; visited[u] = true;for (int e = head[u]; e ; e = edg[e].next)if (!visited[edg[e].v])travel(edg[e].v, distance + edg[e].w); //if there is an edge (u, v) and v has not been visited, then travel(v)
}
int main()
{cin >> n >> m; cnt = 0;memset(visited, false, sizeof visited);memset(head, 0, sizeof head);for (int u, v, w, i = 1; i <= m; i++)cin >> u >> v >> w, add(u, v, w), odeg[u]++, ideg[v]++;for (int i = 1; i <= n; i++)cout << ideg[i] << " " << odeg[i] << endl;for (int i = 1; i <= n; i++)if (!visited[i]) travel(i, 0);
}/*
Given a graph with N nodes and M unidirectional edges.
Each edge e_i starts from u_i to v_i and weights w_i
Output a travelsal from node 1 and output degree of each node.
*/

但是數組模擬必然是逃不開浪費時間過多的，這個事就很討厭了，鄰接矩陣以其優秀的可讀性以及構造性換來了不少空間，唉

我個人現在是這樣的，判斷變數和點數的值，如果差別較大，那么出題人可能是想構造菊花樹之類的，差別較小就意味著稠密，那么寫鄰接矩陣更節省時間（前提是你兩個都能用）

還有一種寫法是用vector

拋去鄰接矩陣不講，如果我們用edg[u][i]表示從u出發的第i條邊，這樣實際上還是O(n^2)的，所以我們要用一個能夠自己改變長度的STL，這樣能讓空間最大化

#include <bits/stdc++.h>using namespace std;const int N = 5005;struct edge {int u, v, w;
};
vector<edge> edg[N]; //edge記錄變長數組記錄的是什么類型 
int ideg[N], odeg[N], n, m, cnt; //cnt: numbers of edges
bool visited[N];void add(int u, int v, int w)
{edg[u].push_back((edge){u, v, w});//一個強制類型轉換 
}
void travel(int u, int distance)
{cout << u << " " << distance << endl; visited[u] = true;for (int e = 0; e < edg[u].size(); e++)//遍歷邊 if (!visited[edg[u][e].v])//以u出發的第e條出邊 travel(edg[u][e].v, distance + edg[u][e].w); //if there is an edge (u, v) and v has not been visited, then travel(v)
}
int main()
{cin >> n >> m; cnt = 0;memset(visited, false, sizeof visited);for (int u, v, w, i = 1; i <= m; i++)cin >> u >> v >> w, add(u, v, w), odeg[u]++, ideg[v]++;for (int i = 1; i <= n; i++)cout << ideg[i] << " " << odeg[i] << endl;for (int i = 1; i <= n; i++)if (!visited[i]) travel(i, 0);
}/*
Given a graph with N nodes and M unidirectional edges.
Each edge e_i starts from u_i to v_i and weights w_i
Output a travelsal from node 1 and output degree of each node.
*/