===
Index
并查集
leetcode 684 : 冗余连接 无向图 leetcode 685 : 冗余连接II 有向图
岛屿数量2
大小为 m*n 的二进制网格，0表示水，1表示陆地，初试全为0。
数组 ps[i] = [ri, ci] 表示第i次操作，将该位置水转换成陆地。
返回一个数组 ans, ans[i] 表示第i次操作后地图中岛屿的数量。
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
const int N = 1e4 + 5;
int p[N];
int find(int x) {
return p[x] == x ? x : p[x] = find(p[x]);
}
class Solution {
public:
vector<int> numIslands2(int m, int n, vector<vector<int>>& ps) {
iota(p,p+m*n,0);
vector<int> vis(m*n), res;
int cnt = 0;
for(auto&e:ps){
int x=e[0], y = e[1], idx = x * n + y;
if(!vis[idx]) {
cnt++;
vis[idx]=1;
for(int i=0;i<4;++i){
int nx=x+dx[i],ny=y+dy[i], nidx = nx * n + ny;
if(nx>=0&&nx<m&&ny>=0&&ny<n && vis[nidx]){
int p1=find(idx),p2=find(nidx);
if(p1^p2) {
p[p1]=p2;
cnt--;
}
}
}
}
res.push_back(cnt);
}
return res;
}
};
拓扑排序
课程表1
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
bool canFinish(int n, vector<vector<int>>& pres) {
vector<vector<int>> G(n);
vector<int> degree(n, 0), bfs;
for (auto& e : pres) {
G[e[1]].push_back(e[0]);
degree[e[0]]++;
}
for (int i = 0; i < n; ++i)
if (!degree[i]) bfs.push_back(i);
for (int i = 0; i < bfs.size(); ++i)
for (int j : G[bfs[i]]) {
if (--degree[j] == 0)
bfs.push_back(j);
}
return bfs.size() == n;
}
课程表2
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
vector<int> findOrder(int n, vector<vector<int>>& pres) {
vector<int> G[n], degree(n, 0), ans;
for (auto& e : pres) {
G[e[1]].push_back(e[0]);
degree[e[0]]++;
}
queue<int> que;
for (int i = 0; i < n; ++i)
if (!degree[i]) que.push(i);
while(!que.empty()){
int tmp = que.front();
ans.push_back(tmp);
que.pop();
for(int x : G[tmp]){
if(--degree[x] == 0) que.push(x);
}
}
return ans.size() == n ? ans : vector<int>();
}
火星词典
现有一种使用英语字母的火星语言，这门语言的字母顺序与英语顺序不同。
给你一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 “” 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
class Solution {
public:
string alienOrder(vector<string>& words) {
map<char,int> indeg;
unordered_map<char, vector<char>> graph;
for(auto& s : words)
for(auto ch: s) indeg[ch] = 0;
for (int i = 1; i < words.size(); ++i) {
string s1 = words[i-1], s2 = words[i];
int size = min(s1.size(), s2.size()), flag = 1;
for (int j = 0; j < size && flag; ++j)
if (s1[j] != s2[j]) {
flag = 0;
++indeg[s2[j]];
graph[s1[j]].emplace_back(s2[j]);
}
if (flag && s1.size() > s2.size()) return "";
}
queue<char> q;
for(auto &[k, v]: indeg) if (v == 0) q.emplace(k);
string ans = "";
while (!q.empty()) {
for (auto &it: graph[q.front()]) if (-- indeg[it] == 0) q.emplace(it);
ans += q.front();
q.pop();
}
return ans.size() == indeg.size() ? ans : "";
}
};
完成拓扑图的最短时间
n个点m条边的有向图，无重边和自环，从u到v的有向边表示需要先完成u，才能开始v。长度为n的数组a，a[i]表示完成i需要的时间，求完成所有节点需要的最短时间。
- 1 <= n <= 1e5
- 1 <= m <= 2e5
- 1 <= a[i] <= 1e5
分析
按照拓扑序dp。
long long minTime(vector<int> a, vector<vector<int>>& edges){
int n = a.size(), cnt = 0;
vector<vector<int>> g(n);
vector<int> deg(n);
vector<long long> dp(n);
for (auto & e : edges) {
g[e[0]].push_back(e[1]);
deg[e[1]]++;
}
queue<int> q;
for (int i = 0; i < n; ++i) {
if (deg[i] == 0) {
q.push(i);
dp[i] = a[i];
cnt++;
}
}
while(q.size()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (--deg[v] == 0) {
q.push(v);
cnt++;
}
dp[v] = max(dp[v], dp[u] + a[v]);
}
}
long long mx = (*max_element(dp.begin(), dp.end()));
return cnt < n ? -1 : mx;
}
克隆图
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
class Node {
public int val;
public List<Node> neighbors;
}
map<Node*,Node*> mp;
Node* cloneGraph(Node* node) {
if(!node) return nullptr;
if(mp.count(node)) return mp[node];
Node* c = new Node(node -> val);
mp[node] = c;
for(int i = 0; i < node -> neighbors.size(); ++ i){
if(node -> neighbors[i])
c -> neighbors.push_back(cloneGraph(node -> neighbors[i]));
}
return c;
}
判断二分图
给定一个无向图graph，当这个图为二分图时返回true。
如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。
graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。
bool isBipartite(vector<vector<int>>& graph) {
int N = graph.size();
int color[N];
memset(color, 0, sizeof(color));
queue<int> que;
for(int i = 0; i < N; i++){
if(color[i]) continue;
color[i] = 1;
que.push(i);
while(!que.empty()){
int q = que.front();
que.pop();
for(int next : graph[q]){
if(color[next] == 0){
color[next] = -color[q];
que.push(next);
}
else if(color[next] == color[q]){
return false;
}
}
}
}
return true;
}
dfs方法：
bool dfs(const vector<vector<int>> &g, int i, int c, vector<int> &v) {
if (v[i] != -1) return v[i] == c;
v[i] = c;
for (int j : g[i]) if (!dfs(g, j, !c, v)) return false;
return true;
}
bool isBipartite(vector<vector<int>>& graph) {
const int n = graph.size();
vector<int> v(n, -1);
for (int i = 0; i < n; i++) if (v[i] == -1 && !dfs(graph, i, 0, v)) return false;
return true;
}
dijkstra算法
- 普通Dijkstra算法时间复杂度为 O(n*n + e)，n是节点数，e是边数。
- 堆优化的Dijkstra算法时间复杂度为 E*log(V),E是边数，V是节点数
- Dijkstra算法不能解决带有负权边的图
struct Edge {
int to, cost;
};
//求s到其他节点的最短路径
int dijkstra(int s, int t) {
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
priority_queue<PAIR, vector<PAIR>, greater<PAIR>> que;
que.push({0,s}); // <cost, id>
while (!que.empty()) {
auto p = que.top();
que.pop();
int v = p.second;
for (auto e : graph[v]) {
if (dis[e.to] > dis[v] + e.cost) {
dis[e.to] = dis[v] + e.cost;
que.push({dis[e.to], e.to});
}
}
}
return dis[t];
}
spfa算法
bellman-ford算法的优化版本，可以处理存在负边权的最短路问题。 最坏情况下的时间复杂度是 O(nm)O(nm)，但实践证明spfa算法的运行效率非常高，期望运行时间是 O(km)O(km)，其中 kk 是常数。 但需要注意的是，在网格图中，spfa算法的效率比较低，如果边权为正，则尽量使用 dijkstra 算法。
struct Edge {
int to, cost;
};
//从s到其他节点的最短路径
void spfa(int s) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
queue<int> q;
vis[s] = 1, dis[s] = 0;
q.push(s); //vector<Edge> G[N];
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = 0; //vis标记该点是否在队列中
for (auto e : G[u]) {
if (dis[e.to] > dis[u] + e.cost) {
dis[e.to] = dis[u] + e.cost;
if (!vis[e.to]) {
q.push(e.to);
vis[e.to] = 1;
}
}
}
}
}
floyd算法
` O(n3)`
void floyd() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
A[i][j] = edge[i][j];
path[i][j] = edge[i][j] == INF ? -1 : i;
}
}
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (A[i][k] + A[k][j] < A[i][j]) {
A[i][j] = A[i][k] + A[k][j];
path[i][j] = path[k][j];
}
}
}
}
}
prim算法
适用于稠密图，时间复杂度 O(n2)。
核心思想：每次挑一条与当前集合相连的最短边。
// vis[i] 表示点i是否在当前生成树集合中
// dis[i] 表示点i到当前集合的最短边的长度
// g[i][j] 表示点i和点j之间边的长度
// 返回值：最小生成树中所有边的总长度
int prim() {
int res = 0;
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[1] = 0;
for (int i = 1; i <= n; ++i) {
int id = -1, min_dist = INF;
// 寻找最短边
for (int j = 1; j <= n; ++j) {
if (!vis[j] && dis[j] < min_dist) {
id = j;
min_dist = dis[j];
}
}
vis[id] = 1;
res += dis[id];
// 用新加入的点更新其余点到生成树的最短边
for (int j = 1; j <= n; j ++ )
if (!vis[j])
dis[j] = min(dis[j], g[id][j]);
}
}
kruskal算法
适用于稀疏图，时间复杂度 O(mlogm)。
核心思想：从小到大挑不多余的边。
struct Edge{
int from, to, cost;
Edge(int f, int t, int c):from(f),to(t),cost(c){}
Edge(){}
bool operator <(const Edge & e)const{
return cost > e.cost;
}
};
int fa[N];
int find(int x){
if(fa[x] == -1) return x;
return fa[x] = find(fa[x]);
}
// 所有边存储在 Edge edges[M];
// 函数返回最小生成树中所有边的总长度
int Kruskal() {
int res = 0;
sort(edge, edge + m);
for (int i = 0; i < m; i ++ ) {
int a = edge[i].from, b = edge[i].to;
if (find(a) != find(b)) {
res += edge[i].cost;
fa[find(a)] = find(b);
}
}
return res;
}
