【每日一题】图的遍历
图的遍历
https://ac.nowcoder.com/acm/problem/52275
解题思路：首先想要一次性走完所有的点，这此图必须是连通图，因此首先需要添加的边的数目就是联通快的数量-1。然后如果每次走两步
想要走完所有的点，则图中必须存在奇数点数的环。我们可以把与奇数环相连的所有环或者链都看作链。我们可以在奇数环中调整走的节奏，
比如 （1，2）（2，3）（3，1）这样是一个奇数环与1相连的有 1-4-5-6-7 我们从1开始走，可以走到5和7然后退回到奇环里，从2开始走可以走4
和6这样就可以遍历完所有的点
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
int vis[maxn],col[maxn];
vector<int>q[maxn];
int flag;
void dfs(int u)
{
for(int i=0;i<q[u].size();i++)
{
int to=q[u][i];
if(!vis[to]) vis[to]=1,col[to]=!col[u],dfs(to);
else if(col[u]==col[to]) flag=1;
}
}
int main()
{
int n,m,t;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
q[a].push_back(b);
q[b].push_back(a);
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(!vis[i]) {
ans++;
vis[i] = col[i] = 1;
dfs(i);
}
}
cout<<ans-flag<<endl;
return 0;
}
谷歌公司福利 178人发布
