properties-graph

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 2D integer array <code>properties</code> having dimensions <code>n x m</code> and an integer <code>k</code>.

Define a function <code>intersect(a, b)</code> that returns the number of distinct integers common to both arrays <code>a</code> and <code>b</code>.

Construct an undirected graph where each index <code>i</code> corresponds to <code>properties[i]</code>. There is an edge between node <code>i</code> and node <code>j</code> if and only if <code>intersect(properties[i], properties[j]) &gt;= k</code>, where <code>i</code> and <code>j</code> are in the range <code>[0, n - 1]</code> and <code>i != j</code>.

Return the number of connected components in the resulting graph.

&nbsp;
Example 1:

<div class="example-block">
Input: properties = [[1,2],[1,1],[3,4],[4,5],[5,6],[7,7]], k = 1

Output: 3

Explanation:

The graph formed has 3 connected components:

<img height="171" src="https://assets.leetcode.com/uploads/2025/02/27/image.png" width="279" />
</div>

Example 2:

<div class="example-block">
Input: properties = [[1,2,3],[2,3,4],[4,3,5]], k = 2

Output: 1

Explanation:

The graph formed has 1 connected component:

<img alt="" src="https://assets.leetcode.com/uploads/2025/02/27/screenshot-from-2025-02-27-23-58-34.png" style="width: 219px; height: 171px;" />
</div>

Example 3:

<div class="example-block">
Input: properties = [[1,1],[1,1]], k = 2

Output: 2

Explanation:

<code>intersect(properties[0], properties[1]) = 1</code>, which is less than <code>k</code>. This means there is no edge between <code>properties[0]</code> and <code>properties[1]</code> in the graph.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n == properties.length &lt;= 100</code></li>
	<li><code>1 &lt;= m == properties[i].length &lt;= 100</code></li>
	<li><code>1 &lt;= properties[i][j] &lt;= 100</code></li>
	<li><code>1 &lt;= k &lt;= m</code></li>
</ul>

numberOfComponents

Properties Graph

Depth-First Search

Breadth-First Search

Union Find

Graph

Array

Hash Table

给你一个二维整数数组 <code>properties</code>，其维度为 <code>n x m</code>，以及一个整数 <code>k</code>。

定义一个函数 <code>intersect(a, b)</code>，它返回数组 <code>a</code> 和 <code>b</code> 中 共有的不同整数的数量 。

构造一个 无向图，其中每个索引 <code>i</code> 对应 <code>properties[i]</code>。如果且仅当 <code>intersect(properties[i], properties[j]) &gt;= k</code>（其中 <code>i</code> 和 <code>j</code> 的范围为 <code>[0, n - 1]</code> 且 <code>i != j</code>），节点 <code>i</code> 和节点 <code>j</code> 之间有一条边。

返回结果图中 连通分量 的数量。

&nbsp;

示例 1：

<div class="example-block">
输入： properties = [[1,2],[1,1],[3,4],[4,5],[5,6],[7,7]], k = 1

输出： 3

解释：

生成的图有 3 个连通分量：

<img src="https://pic.leetcode.cn/1742665594-CDVPWz-image.png" style="width: 279px; height: 171px;" />
</div>

示例 2：

<div class="example-block">
输入： properties = [[1,2,3],[2,3,4],[4,3,5]], k = 2

输出： 1

解释：

生成的图有 1 个连通分量：

<img alt="" src="https://pic.leetcode.cn/1742665565-NzYlYH-screenshot-from-2025-02-27-23-58-34.png" style="width: 219px; height: 171px;" />
</div>

示例 3：

<div class="example-block">
输入： properties = [[1,1],[1,1]], k = 2

输出： 2

解释：

<code>intersect(properties[0], properties[1]) = 1</code>，小于 <code>k</code>。因此在图中 <code>properties[0]</code> 和 <code>properties[1]</code> 之间没有边。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n == properties.length &lt;= 100</code></li>
	<li><code>1 &lt;= m == properties[i].length &lt;= 100</code></li>
	<li><code>1 &lt;= properties[i][j] &lt;= 100</code></li>
	<li><code>1 &lt;= k &lt;= m</code></li>
</ul>