欧拉路径

T1

这道题看着就比较板。需要让每条路都走一遍，不就是求个欧拉回路么？不过，看到题目要求：

Bassie从 $1$ 号农场开始巡逻，每条路必须从两个方向各走恰好一遍，最后回到 $1$ 号农场

虽然这道题需要我们把一条边两个方向都走一边，但我们不能被这种神奇的要求所折服。既然一条边两个方向都要走一遍，那么建边的时候就建双向边，跑欧拉回路不就行了吗？

还有，在路上所经过的点需要保存下来倒序输出。可以使用数组保存，队列和栈也可以

CPP

vector<int> nbr[N];
queue<int> ans;
void dfs(int cur)
{
	for(int i=0;i<nbr[cur].size();i++)
	{
		int nxt=nbr[cur][i];
		if(nxt)
		{
			nbr[cur][i]=0;
			dfs(nxt);
		}
	}
	ans.push(cur);
	return ;
}

核心代码↑

T2

这道题看着十分吓人，什么叫分组跑图啊？我怎么知道会跑这么多次？但实则不然。

既然这道题这么问了，那么肯定会有数据找不到欧拉回路。我们知道，欧拉回路中出度、入度的点为

1

的点最多只有两个点（起点和终点），否则没有这一种点。那么我们不妨直接从

1

到

n

跑欧拉回路，记录每个连通图中的点数。

跑完图后，有下列几种情况：

连通图节点数不大于 $1$ （为孤点）就没必要继续跑，可以跳过，不计贡献
如果这个连通图的奇数度的节点数量为 $0$ ，那么这个图就是个欧拉回路，贡献加一
如果奇数点的数量不为 $0$ 。由于一个欧拉回路最多只能处理掉两个奇数度数节点，所以贡献为：奇数节点数量 $/2$

CPP

void dfs(int cur)
{
	vis[cur]=true;
	if(nbr[cur].size()%2==1)
	{
		cnt++;
	}
	for(int i=0;i<nbr[cur].size();i++)
	{
		int nxt=nbr[cur][i];
		if(vis[nxt]==false)
		{
			dfs(nxt);
		}
	}
	return ;
}

CPP

for(int i=1;i<=n;i++)
{
  if(vis[i]==true)
  {
    continue;
  }
  if(nbr[i].size()==0)
  {
    continue;
  }
  cnt=0;
  dfs(i);
  if(cnt==0)
  {
    ans++; 
  }
  else
  {
    ans+=cnt/2;
  }
}
return ans;
}

T3

题意：总共有n个节点，m条路径，要求其中m−2条路径走两遍，剩下2条路径仅走一遍，问不同的路径总数有多少，如果仅走一遍的两条边不同则将这两条路径视为不同

我们可以直接把边拆成两条，显然这样每个点的度数都是偶数。那么这一整张图就构成了欧拉路

既然我们知道这是个欧拉回路，那么删去的两条边必连在同一个点上。这样保证了有两个点的度数变成奇数的情况下，和这些节点连的点度数-2，仍然为偶数，整张图依然是欧拉路

判断连通，我们可以直接使用并查集或者

dfs

，接下来就是计算贡献了

我们假设自环的数量为

x

，边上点的度数（出入度）为

y

那么由下面三种情况会产生贡献：

两个自环对答案做贡献，那么总贡献就等于 $(x^2-x)/2$
一个自环一条边，贡献有 $x*m-x^2$
两条边可贡献 $(y^2-y)/2$

文章操作

T1

T2

T3

相关推荐

评论

欧拉路径