題目

給出一個(gè)連通無向圖，求最多能刪掉多少條邊后還是連通圖。

---

輸入

4(頂點(diǎn)數(shù)) 6(邊數(shù))
1 2 (表示一條點(diǎn)1到點(diǎn)2的線)
1 3
1 4
2 3
2 4
3 4

輸出

3

---

dfs解題思路

這道題其實(shí)不用dfs更簡單，但是畢竟例題還是用一下吧。
首先我們?nèi)绻竭_(dá)一個(gè)點(diǎn)便標(biāo)記一下，等到下一次在到這個(gè)點(diǎn)時(shí)就可以確定這條線是不需要的（因?yàn)橛衅渌姆椒梢缘竭_(dá)）

---

dfs代碼

#include<cstdio> using namespace std; int walk[101],a[101][101],x,y,n,m,s; void dfs(int x) {walk[x]=true;//標(biāo)記已有方法可以到達(dá)for (int i=1;i<=n;i++){if (a[x][i]==true && i!=x)//如果可以到達(dá){a[x][i]=false;a[i][x]=false;//標(biāo)記為已經(jīng)搜過if (walk[i]) s++;//如果有方法可以到達(dá)就刪掉這條邊else dfs(i);//不然就搜索}} } int main() {scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){scanf("%d%d",&x,&y);a[x][y]=true;a[y][x]=true;//表示兩點(diǎn)連通}dfs(1);//搜索printf("%d",s);//輸出 }

---

其他解題思路

其實(shí)根據(jù)推理，輸出6-4+1(m-n+1)就可以的

總結(jié)

以上是生活随笔為你收集整理的ssl1217-删边【图论，dfs】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。