[图论与代数结构 801] 无向图的块

Luogu
IDLGB3610
Time1000ms
Memory512MB
DifficultyP4
图论Tarjan双连通分量
在离散数学课程的学习中,大家学习了无向图中”割点“和“块”的定义,现在来检查一下大家的学习情况。 给定一张 $n$ 个点 $m$ 条边的无向图,点的编号从 $1$ 到 $n$ ,可能存在重边和自环,不保证是一张连通图。现在,请你求出这张图所有的块。 注意,我们不把一个没有任何与其相连边的点看成割点;因此,一个单独的点构成的连通块不被看成是块。你可以通过样例理解这个事情。 在输出的时候,我们规定这么一个输出的顺序:首先,对于一个块,我们把该块中所有点按照编号从小到大排序;然后,对于两个块,我们规定,把点按照顺序拿出来排成一个序列,字典序较小的排在前面。这样,我们就可以对所有块规定了一个顺序。最终输出就按照这样的顺序输出。 有关字典序的定义,可以在搜索引擎上查找,或者参考[百度百科_字典序](https://baike.baidu.com/item/%E5%AD%97%E5%85%B8%E5%BA%8F/7786229)。 ## Input 第一行两个正整数 $n$ 和 $m$ ,分别表示给定无向图的点数和边数。 接下来 $m$ 行,每行两个正整数 $u$ 和 $v$ 表示一条连接这两个点的无向边。 ## Output 第一行一个正整数 $Cnt$ 表示答案,即图中块的个数。 接下来 $Cnt$ 行,第 $i$ 行输出若干个正整数,表示第 $i$ 个块中的所有点。注意同一个块点的编号按照从小到大的顺序输出。按照题目中规定的字典序顺序输出块。 [samples] ## Note 本题没有部分分。 对于所有数据,满足 $1\leq n \leq 50000$,$1 \leq m \leq 300000$,保证输入的图合法且满足题目中的限制条件。
Samples
Input #1
7 7
5 6
1 2
3 5
1 4
3 1
4 5
2 5
Output #1
2
1 2 3 4 5
5 6
API Response (JSON)
{
  "problem": {
    "name": "[图论与代数结构 801] 无向图的块",
    "description": {
      "content": "在离散数学课程的学习中,大家学习了无向图中”割点“和“块”的定义,现在来检查一下大家的学习情况。 给定一张 $n$ 个点 $m$ 条边的无向图,点的编号从 $1$ 到 $n$ ,可能存在重边和自环,不保证是一张连通图。现在,请你求出这张图所有的块。 注意,我们不把一个没有任何与其相连边的点看成割点;因此,一个单独的点构成的连通块不被看成是块。你可以通过样例理解这个事情。 在输出的时候,我们规",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3610"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在离散数学课程的学习中,大家学习了无向图中”割点“和“块”的定义,现在来检查一下大家的学习情况。\n\n给定一张 $n$ 个点 $m$ 条边的无向图,点的编号从 $1$ 到 $n$ ,可能存在重边和自环,不保证是一张连通图。现在,请你求出这张图所有的块。\n\n注意,我们不把一个没有任何与其相连边的点看成割点;因此,一个单独的点构成的连通块不被看成是块。你可以通过样例理解这个事情。\n\n在输出的时候,我们规...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments