欧拉路径

· · 个人记录

T1

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

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

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

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

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跑欧拉回路，记录每个连通图中的点数。

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

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 ;
}
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

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