547. Number of Provinces

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

 

Example 1:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

 

Constraints:

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] is 1 or 0.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

 A:

一开始理解错误。 以为是关于edge这个matrix的 岛屿的数量。

但是，这里，从a->b 需要再找每个从b开始的边的dfs

class Solution {

public:

int findCircleNum(vector<vector<int>>& isConnected) {

int n = isConnected.size();

int res = 0;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if (isConnected[i][j]) {

dfs(isConnected, i, j);

res++;

}

}

}

return res;

}

private:

void dfs(vector<vector<int>>& isConnected, int i, int j) {

int n = isConnected.size();

isConnected[i][j] = 0;

for (int k = 0; k < n; k++) {

if (isConnected[j][k] == 1)

dfs(isConnected, j, k);

}

}

};

1971. Find if Path Exists in Graph ---E

 There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

 

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2

Example 2:

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.

 

Constraints:

• 1 <= n <= 2 * 105
• 0 <= edges.length <= 2 * 105
• edges[i].length == 2
• 0 <= ui, vi <= n - 1
• ui != vi
• 0 <= source, destination <= n - 1
• There are no duplicate edges.
• There are no self edges.

A：

首先是一个找，然后去找边。 结果超时了

class Solution {

public:

bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {

deque<int> deck;

deck.push_back(source);

vector<bool> found(n, false);

while (not deck.empty()) {

auto a = deck.front();

if (a == destination)

return true;

found[a] = true;

deck.pop_front();

for (auto edge : edges) {

if (edge[0] == a) {

if (not found[edge[1]]) {

found[edge[1]] = true;

deck.push_back(edge[1]);

}

} else if (edge[1] == a) {

if (not found[edge[0]]) {

found[edge[0]] = true;

deck.push_back(edge[0]);

}

}

}

}

return false;

}

};

--------改进。 在里面for 循环部分--------

因此，把边的链表，写成每个顶点， 包含其另一端的定点的set

class Solution {

public:

bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {

queue<int> Q;

Q.push(source);

vector<bool> found(n, false);

found[source] = true;

unordered_map<int, unordered_set<int>> M;

for(auto edge : edges){

int a = edge[0], b = edge[1];

M[a].insert(b);

M[b].insert(a);

}

while (not Q.empty()) {

auto a = Q.front();

if (a == destination)

return true;

Q.pop();

for(auto b : M[a]){

if(not found[b]){

found[b] = true;

Q.push(b);

}

}

}

return false;

}

};

然而，还是击败了不到10%。

算法复杂度上，不会有大的改进了。

这次把unordered_map用vector来表示。 也就是改变edges的表示方式

class Solution {

public:

bool validPath(int n, vector<vector<int>>& edges, int source,

int destination) {

if (source == destination)

return true;

vector<int> V;

V.emplace_back(source);

vector<bool> found(n, false);

found[source] = true;

vector<vector<int>> M(n);

for (auto edge : edges) {

int a = edge[0], b = edge[1];

M[a].emplace_back(b);

M[b].emplace_back(a);

}

for (int i = 0; i < V.size(); i++) {

auto a = V[i];

for (auto b : M[a]) {

if (not found[b]) {

if (b == destination)

return true;

found[b] = true;

V.emplace_back(b);

}

}

}

return false;

}

};

但是也只是beat了51%的。 算了，就这样吧。 看图表，也都差不多挤在一起

PS： 这个，我们用的是BFS的思想。

别人有用dfs递归的。