哥尼斯堡的“七橋問題
- 題目
- 答案
- 總結
題目
答案
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int pre[1005],n,m;
vector<int> vec[1005];
int Find(int x)
{
if(pre[x]==-1) return x;
else return pre[x]=Find(pre[x]);
}
void combine(int x,int y)
{
int tmp1=Find(x),tmp2=Find(y);
if(tmp1!=tmp2)
{
pre[tmp2]=tmp1;
}
}
int main()
{
cin>>n>>m;
memset(pre,-1,sizeof pre);
while(m--)
{
int x,y;
cin>>x>>y;
combine(x,y);
vec[x].push_back(y);
vec[y].push_back(x);
}
int cnt1=0,cnt2=0;//cnt1統計奇數點，cnt2統計根點
for(int i=1;i<=n;i++)
{
if(vec[i].size()%2) cnt1++;
if(Find(i)==i) cnt2++;
}
if(cnt1==0&&cnt2==1) printf("1");
else printf("0");
}
總結
這道題采用的是并查集的方法，每個節點的度數就是它向量的size
但需要注意的是，這道題的Find函式如果使用回圈，會出現運行超時的問題
回圈代碼如下：
int Find(int x)
{
while(pre[x]!=-1)
x=pre[x];
return x;
}
所以我們要對Find函式優化，將其改為改良版的遞回
代碼如下：
int Find(int x)
{
if(pre[x]==-1) return x;
else return pre[x]=Find(pre[x]);
}
大家可能會問，常理上，遞回不是比回圈慢嗎？怎么反而能節約時間呢？
因為，遞回的Find函式，除了實作Find外，還有一個作用就是優化
我們來看這行代碼：
else return pre[x]=Find(pre[x]);
參考一下大佬的話：這句是先把find到的x賦值給pre[x]的，查找路徑上的每個點，下一次找的時候，就能直接找到終點了
再解釋一下就是因為此函式找到值為-1的節點就回傳，所以所有的節點在遞回的賦值中最終都指向了值為-1的節點，為后續的Find節約了時間
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278561.html
標籤：其他