day-65 代码随想录算法训练营（19）图论 part 04

463.岛屿的周长

分析：

• 1.陆地的旁边是海面，存在周长
• 2.陆地在边界上，存在周长

思路一：深度优先遍历

• 1.通过记录访问情况来访问数据

class Solution {
public:
    int direct[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    int res=0;
    void dfs(vectorint>>&grid,vectorbool>>&visted,int x,int y){
        for(int i=0;i<4;i++){
            int nextx=x+direct[i][0];
            int nexty=y+direct[i][1];
            if(nextx>=0 && nextxsize() && nexty>=0 && nexty0].size()){
                if(!visted[nextx][nexty]){
                    if(grid[nextx][nexty]==0) res++;//那一边是海面
                    else{
                        visted[nextx][nexty]=true;
                        dfs(grid,visted,nextx,nexty);
                    }
                }
            }
            else res++;//那一边是边界
        }
    }
    int islandPerimeter(vectorint>>& grid) {
        int n=grid.size(),m=grid[0].size();
        vectorbool>>visted(n,vector<bool>(m,false));
        for(int i=0;i
            for(int j=0;j
                if(!visted[i][j] && grid[i][j]==1){
                    visted[i][j]=true;
                    dfs(grid,visted,i,j);
                }
            }
        }
        return res;
    }
};

1971.寻找图中是否存在路径

分析：

• 寻找两个节点间是否存在路径，就是寻找两个节点是否在同一集合中

思路一：并查集

• 1.初始化集合
• 2.把各个节点进行连接
• 3.寻根判断

class Solution {
public:
    int n=200005;
    vector<int>father=vector<int>(n,0);
    void init(){//并查集初始化
        for(int i=0;i
    }
    int find(int u){//并查集寻根
        return u==father[u]?u:father[u]=find(father[u]);
    }
    bool isSame(int u,int v){
        u=find(u);
        v=find(v);
        return u==v;
    }
    void join(int u,int v){//连接两个节点
        u=find(u);
        v=find(v);
        if(u==v) return;//说明已经存在连接
        father[u]=v;//进行连接
    }
    bool validPath(int n, vectorint>>& edges, int source, int destination) {
        init();
        for(int i=0;isize();i++) join(edges[i][0],edges[i][1]);//连接节点
        return isSame(source,destination);//寻根判断
    }
};

684.冗余连接

分析：

• 1.出现两个节点在同一集合，即有冗余

思路一：并查集

• 1.初始化
• 2.边添加边判断

class Solution {
public:
    vector<int>father=vector<int>(1001,0);
    void init(){
        for(int i=0;i<1001;i++) father[i]=i;
    }
    int find(int u){//寻根
        return u==father[u]?u:father[u]=find(father[u]);
    }
    bool isSame(int u,int v){//判断是否同一集合
        u=find(u);
        v=find(v);
        if(u==0 && v==0) return false;
        return u==v;
    }
    void join(int u,int v){//连接节点
        u=find(u);
        v=find(v);
        if(u==v) return;
        father[u]=v;
    }
    vector<int> findRedundantConnection(vectorint>>& edges) {
        init();//初始化！！！
        int n=edges.size();
        for(int i=0;i
            if(isSame(edges[i][0],edges[i][1])) return edges[i];//出现两个节点在同一集合
            else join(edges[i][0],edges[i][1]);
        }
        return vector<int>();
    }
};

685.冗余连接 || 

分析：

• 只存在一条冗余边，有三种情况：

• 1.入度可以通过遍历获取
• 2.环可以通过判断两节点是否在同一集合获取 

思路一：并查集

• 1.先获取所有节点的入度
• 2.存在节点入度为2：
  • 倒序找出入度为 2 的节点边
  • 节点边不考虑时，判断图是否为树
• 3.不存在节点入度为2：
  • 判断删除那一条边存在环，直接返回

class Solution {
public:
    static const int N=1010;
    int father[N];
    int n;
    void init(){//初始化
        for(int i=1;i<=n;++i) father[i]=i;
    }
    int find(int u){//寻根
        return u==father[u]?u:father[u]=find(father[u]);
    }
    bool same(int u,int v){//判断是否在同一集合
        u=find(u);
        v=find(v);
        return u==v;
    }
    void join(int u,int v){//连接两个节点
        u=find(u);
        v=find(v);
        if(u==v) return;
        father[u]=v;
    }
    vector<int> getMoveEdge(const vectorint>>&edges){//获取要删除的冗余边
        init();
        for(int i=0;i
            if(same(edges[i][0],edges[i][1])) return edges[i];//已经存在同一集合，所以此线冗余
            join(edges[i][0],edges[i][1]);
        }
        return {};//不存在冗余
    }
    bool judge(const vectorint>>&edges,int deleteEdge){//判断删除该边是否是树
        init();
        for(int i=0;i
            if(i==deleteEdge) continue;//删除就不考虑
            if(same(edges[i][0],edges[i][1])) return false;//仍然存在同一集合，绝对不是树
            join(edges[i][0],edges[i][1]);
        }
        return true;
    }
 
    vector<int> findRedundantDirectedConnection(vectorint>>& edges) {
        n=edges.size();
        int inDegree[N]={0};
        vector<int>mid;
        for(int i=0;i1]]++;//记录入度
        for(int i=n-1;i>=0;i--){//从右侧开始记录
            if(inDegree[edges[i][1]]==2) mid.push_back(i);//记录入度为2的节点的下标
        }
        if(mid.size()>0){//存在入度为2的节点
            if(judge(edges,mid[0])) return edges[mid[0]];//最右边的边不考虑，图为树
            else return edges[mid[1]];
        }
        return getMoveEdge(edges);
    }
};