图论第6天

提高效率!!!两道题+看并查集

841.钥匙和房间

忘了把visited 加引用了：&

class Solution {
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {vector<int>visited(rooms.size(),false);dfs(rooms,visited,0);for(int i = 0;i < rooms.size();i++){if(visited[i] == false)return false;}return true;}void dfs(vector<vector<int>>& rooms,vector<int>&visited,int key){if(visited[key] == true)return;visited[key] = true;vector<int>keys = rooms[key];for(int i = 0; i < keys.size();i++){dfs(rooms,visited,keys[i]);}}
};

463. 岛屿的周长

第一是不要算重边即可。

第二是有两个挨着的岛屿就总周长减2。

第三这题不用dfs or bfs。

class Solution {
public:int islandPerimeter(vector<vector<int>>& grid) {int island_num = 0;int count = 0;for(int i = 0;i < grid.size();i++){for(int j = 0;j < grid[0].size();j++){if(grid[i][j] == 1){island_num++;if((i - 1) >= 0 && grid[i-1][j] == 1)count++;if((j-1) >= 0 && grid[i][j-1] == 1)count++;}}}return island_num * 4 - count * 2;}
};

图论还剩三道题，明天争取拿下！！！