2、已知有m个顶点，相邻的两个顶点之间有一条边相连接，首位顶点也有一条边连接，这样就构成了一个圆环。
现在有一个二维数组M[][]，M[i][j]=1时，表明第i和j个节点之间有条边存在，M[i][j]=0时，表明第i和j个节点之间没有边存在，其中 M[i][i]=0，M[i][j]=M[j][i]，输入为一个二维数组M[][]和顶点的个数n，试着判断该图中是否存在两个圆环，且两个圆环彼此之间没有公共点。
bool IsTwoCircle(int **M,int n)
{
......
}
5 个解决方案
#1
问了N遍了，还最新
#2
有人问过吗？
#3
1,哥已经写过,3层循环的DP,int dp[i][j][limit],表示i,j开始不超过limit的最大和,从右下角开始往上推:
dp[i][j][limit]=max{dp[i+1][j][limit-value[i][j]],dp[i][j+1][limit-value[i][j]]}+value[i][j];
初始化dp[][][]为0,0的意思是不可能达到右下角的意思,DP最外循环是i=(row...0),中循环是j=(col...0),内循环是limit=(0...K).
最后结果是dp[0][0][k],如果为0表示无法到达右下角,如果非0则为不超过K的最大价值.
2,先思考思考。
dp[i][j][limit]=max{dp[i+1][j][limit-value[i][j]],dp[i][j+1][limit-value[i][j]]}+value[i][j];
初始化dp[][][]为0,0的意思是不可能达到右下角的意思,DP最外循环是i=(row...0),中循环是j=(col...0),内循环是limit=(0...K).
最后结果是dp[0][0][k],如果为0表示无法到达右下角,如果非0则为不超过K的最大价值.
2,先思考思考。
#4
有了,办法比较笨,这个问题就是无向图找回路问题.
可以对每个顶点做深搜,进入一个顶点给它标记灰色,离开一个顶点标记回白色,如果某个顶点的邻接顶点是灰色,那么就是一个环,为了表示这个环,我们在深搜过程中还需要维护一个pre域即可.
这个DFS找环倒没什么可说的,反向边问题.
至于找出所有的环之后,PS：一个环可能从不同的方向被获得,所以结果中可能1种环对应2个结果.
之后就是过滤掉我上边说的1环对2结果,这个很简单,把两个序列中某一个逆序之后比较相等就说明是同一个环.
再之后如何判断不想交的环,可以用并查集,首先每个环内部所有点并在一起,之后只要判断每两对环是否属于同一个集合即可.
可以对每个顶点做深搜,进入一个顶点给它标记灰色,离开一个顶点标记回白色,如果某个顶点的邻接顶点是灰色,那么就是一个环,为了表示这个环,我们在深搜过程中还需要维护一个pre域即可.
这个DFS找环倒没什么可说的,反向边问题.
至于找出所有的环之后,PS：一个环可能从不同的方向被获得,所以结果中可能1种环对应2个结果.
之后就是过滤掉我上边说的1环对2结果,这个很简单,把两个序列中某一个逆序之后比较相等就说明是同一个环.
再之后如何判断不想交的环,可以用并查集,首先每个环内部所有点并在一起,之后只要判断每两对环是否属于同一个集合即可.
#5
额,有问题,其实一种环可能对应N种结果.... 这个怎么过滤呢... 办法就是对于找出的所有环,
对于每个环,找到环中编号最小的结点,之后做循环位移让最小的结点排列在第一位.
这样统一之后再去重就很简单了.
#1
问了N遍了，还最新
#2
有人问过吗？
#3
1,哥已经写过,3层循环的DP,int dp[i][j][limit],表示i,j开始不超过limit的最大和,从右下角开始往上推:
dp[i][j][limit]=max{dp[i+1][j][limit-value[i][j]],dp[i][j+1][limit-value[i][j]]}+value[i][j];
初始化dp[][][]为0,0的意思是不可能达到右下角的意思,DP最外循环是i=(row...0),中循环是j=(col...0),内循环是limit=(0...K).
最后结果是dp[0][0][k],如果为0表示无法到达右下角,如果非0则为不超过K的最大价值.
2,先思考思考。
dp[i][j][limit]=max{dp[i+1][j][limit-value[i][j]],dp[i][j+1][limit-value[i][j]]}+value[i][j];
初始化dp[][][]为0,0的意思是不可能达到右下角的意思,DP最外循环是i=(row...0),中循环是j=(col...0),内循环是limit=(0...K).
最后结果是dp[0][0][k],如果为0表示无法到达右下角,如果非0则为不超过K的最大价值.
2,先思考思考。
#4
有了,办法比较笨,这个问题就是无向图找回路问题.
可以对每个顶点做深搜,进入一个顶点给它标记灰色,离开一个顶点标记回白色,如果某个顶点的邻接顶点是灰色,那么就是一个环,为了表示这个环,我们在深搜过程中还需要维护一个pre域即可.
这个DFS找环倒没什么可说的,反向边问题.
至于找出所有的环之后,PS：一个环可能从不同的方向被获得,所以结果中可能1种环对应2个结果.
之后就是过滤掉我上边说的1环对2结果,这个很简单,把两个序列中某一个逆序之后比较相等就说明是同一个环.
再之后如何判断不想交的环,可以用并查集,首先每个环内部所有点并在一起,之后只要判断每两对环是否属于同一个集合即可.
可以对每个顶点做深搜,进入一个顶点给它标记灰色,离开一个顶点标记回白色,如果某个顶点的邻接顶点是灰色,那么就是一个环,为了表示这个环,我们在深搜过程中还需要维护一个pre域即可.
这个DFS找环倒没什么可说的,反向边问题.
至于找出所有的环之后,PS：一个环可能从不同的方向被获得,所以结果中可能1种环对应2个结果.
之后就是过滤掉我上边说的1环对2结果,这个很简单,把两个序列中某一个逆序之后比较相等就说明是同一个环.
再之后如何判断不想交的环,可以用并查集,首先每个环内部所有点并在一起,之后只要判断每两对环是否属于同一个集合即可.
#5
额,有问题,其实一种环可能对应N种结果.... 这个怎么过滤呢... 办法就是对于找出的所有环,
对于每个环,找到环中编号最小的结点,之后做循环位移让最小的结点排列在第一位.
这样统一之后再去重就很简单了.