[图论与代数结构 701] 强连通分量

Luogu
IDLGB3609
Time1000ms
Memory512MB
DifficultyP4
强连通分量Tarjan
给定一张 $n$ 个点 $m$ 条边的有向图,求出其所有的强连通分量。 **注意,本题可能存在重边和自环。** ## Input 第一行两个正整数 $n$,$m$,表示图的点数和边数。 接下来 $m$ 行,每行两个正整数 $u$ 和 $v$ 表示一条边。 ## Output 第一行一个整数表示这张图的强连通分量数目。 接下来每行输出一个强连通分量。第一行输出 $1$ 号点所在强连通分量,第二行输出 $2$ 号点所在强连通分量,若已被输出,则改为输出 $3$ 号点所在强连通分量,以此类推。每个强连通分量按节点编号大小输出。 [samples] ## Note 对于所有数据,$1 \le n \le 10000$,$1 \le m \le 100000$。
Samples
Input #1
6 8
1 2
1 5
2 6
5 6
6 1
5 3
6 4
3 4
Output #1
3
1 2 5 6
3
4
API Response (JSON)
{
  "problem": {
    "name": "[图论与代数结构 701] 强连通分量",
    "description": {
      "content": "给定一张 $n$ 个点 $m$ 条边的有向图,求出其所有的强连通分量。 **注意,本题可能存在重边和自环。**",
      "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": "LGB3609"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一张 $n$ 个点 $m$ 条边的有向图,求出其所有的强连通分量。\n\n**注意,本题可能存在重边和自环。**\n\n## Input\n\n第一行两个正整数 $n$,$m$,表示图的点数和边数。\n\n接下来 $m$ 行,每行两个正整数 $u$ 和 $v$ 表示一条边。\n\n## Output\n\n第一行一个整数表示这张图的强连通分量数目。\n\n接下来每行输出一个强连通分量。第一行输出 $1$ 号点所在强连通分...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments