资源共享网站开发,wordpress搜索次数,沈阳自助建站模板,wordpress刷留言题目
给出一个连通无向图#xff0c;求最多能删掉多少条边后还是连通图。 输入
4(顶点数) 6(边数) 1 2 (表示一条点1到点2的线) 1 3 1 4 2 3 2 4 3 4
输出
3 dfs解题思路
这道题其实不用dfs更简单#xff0c;但是毕竟例题还是用一下吧。 首先我们如果到达一个点便…题目
给出一个连通无向图求最多能删掉多少条边后还是连通图。 输入
4(顶点数) 6(边数) 1 2 (表示一条点1到点2的线) 1 3 1 4 2 3 2 4 3 4
输出
3 dfs解题思路
这道题其实不用dfs更简单但是毕竟例题还是用一下吧。 首先我们如果到达一个点便标记一下等到下一次在到这个点时就可以确定这条线是不需要的因为有其他的方法可以到达 dfs代码
#includecstdio
using namespace std;
int walk[101],a[101][101],x,y,n,m,s;
void dfs(int x)
{walk[x]true;//标记已有方法可以到达for (int i1;in;i){if (a[x][i]true i!x)//如果可以到达{a[x][i]false;a[i][x]false;//标记为已经搜过if (walk[i]) s;//如果有方法可以到达就删掉这条边else dfs(i);//不然就搜索}}
}
int main()
{scanf(%d%d,n,m);for (int i1;im;i){scanf(%d%d,x,y);a[x][y]true;a[y][x]true;//表示两点连通}dfs(1);//搜索printf(%d,s);//输出
} 其他解题思路
其实根据推理输出6-41(m-n1)就可以的
