Leetcode: 1627. Graph Connectivity With Threshold

打起精神来,今天有比昨天更好一点!

这题,我对他的解释是,现在有未知的图,我有些node跟node之间的线索,用线索去把这个图的全貌拼凑出来(讲得好像在解谜一样XD)。

简单讲就是现在这张图,只有它送过来指定的node配对中,两点的公因数有大於threshold,两点之间就有连线。
 
 
 

思路

感觉这题是在图的基础上,问你怎麽找两数的公因数。
 
 
 

看题目时,眼睛要在睁大一点

因为题目问的是:请问我指定的配对有没有path可以连通,所以两点之间即使没有直达的edge,也可能有path存在,所以不能单单只是找最大公因数。

所以思路会改为,先判断公因数,更新图,如果没有符合条件的公因数,再用traversal找一遍。
 

 
 

程序题

class Solution {
public:
    vector<int> parent ;
    
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        vector<bool> answer(queries.size());
   
        if (!threshold) {
            fill(answer.begin(), answer.end(), true);
            return answer;
        }
        
        parent = vector<int>(n+1) ;
        for (int i = 0; i < parent.size(); i++) parent[i] = i;
        
        for (int z = threshold + 1; 2*z <= n; z++)
            for (int x = 2; x*z <= n; x++) 
                unionfunc(z, x*z);
        
        for (int i = 0; i < queries.size(); i++)
            answer[i] = find(queries[i][0]) == find(queries[i][1]);
        
        return answer;
    }
private:
    int find(int u) {
        if (parent[u] != u)
            return find(parent[u]);
        return u;
    }
    
    void unionfunc(int u, int v) {
        parent[find(v)] = parent[find(u)];
    }
};


补充

这题跟第一天Graph-Tree: uva 615 Is It A Tree?一样使用并查集,也体会到我还没有很熟这种资料结构,至少我没办法像adj list那样熟练。

并查集是了解了没错,但是参不透中间那两个for是干啥用的!

 

C++ 笔记

Line 30: Char 10: error: declaration of anonymous union must be a definition
void union(vector& parent, int u, int v) {

union是保留字

 
 
参考:
https://leetcode.com/problems/graph-connectivity-with-threshold/discuss/899462/Extremely-useful-Union-Find-class-Feel-Free-to-Reuse
https://www.youtube.com/watch?v=ayW5B2W9hfo


<<:  Day19 - 使用Django进行自动化测试 (1)

>>:  【Day 16】InnoDB indexing

[NestJS 带你飞!] DAY15 - Dynamic Module

前面有介绍过 Module 的一些基本使用方式,然而有一项非常强大的功能没有被提及,就是 动态模组(...

SystemC: 开始罗,再等等!

CPU 是以 clock cycle 为单位,每一小段时间做一点事 等等!我们一开始就没提到过时间啊...

铁人赛 Day7 -- PHP SQL基本语法(二) -- Session 你到底可以干麻

session 简单来说就是可以在多个页面存取同一位使用者连线资料。他其实和 cookie 很像 但...

Day26 - 动态模型 part1 (LSTM)

动态模型我们会使用 LSTM-based 架构,并分成两种: Basic LSTM Last-fra...

Day 03 Benefits and Constraints of Embedded Systems

Compare and contrast CPU, MCU, and embedded syste...