给定一个有向图,找出一个子图使得对于该子图的任意两个点$u$,$v$,$u$可以到达$v$或$v$可以到达$u$,判断这样的最大子图的节点个数。
链接
登不了UVa,只能用洛谷的链接惹qwq
UVa 11324
题解
求出图中的强连通分量,缩点,变成DAG。每一个点给一个权值,权值设为每个强连通分量的结点数。最后用记忆化搜索给出最长路。
求最长路时写炸了,输入居然可以决定最长路的总权值
代码
1 |
|
技不如人,被吊打
给定一个有向图,找出一个子图使得对于该子图的任意两个点$u$,$v$,$u$可以到达$v$或$v$可以到达$u$,判断这样的最大子图的节点个数。
登不了UVa,只能用洛谷的链接惹qwq
UVa 11324
求出图中的强连通分量,缩点,变成DAG。每一个点给一个权值,权值设为每个强连通分量的结点数。最后用记忆化搜索给出最长路。
求最长路时写炸了,输入居然可以决定最长路的总权值
1 | #include<bits/stdc++.h> |