分离路径

题意

给你一个无向图，让你求出无向图内任意两点之间都有两条路径需要建立的最少边数。

分析

如果图是有向图的话，那么图中的任一两个点之间都有两条路径，如果我们将有向边只看作可以改变方向的无向边的话，那么图就可以进行缩点。

缩点之后，图中的任一两点都是只有一条路径的。

那么如何去建立最少的边满足条件呢？

如果有n个叶子的话。答案就是 n/2的向上取整。

为什么？

因为如果如果我们将i号节点与j号节点相连，那么i号节点到j号节点就有两条边。并且其他节点到i号节点可以直接过去，也可以通过j号节点过去。

有向图缩点

void tarjan(int x)
{
  dfn[x]=low[x]=++id;
  sta[++top]=x;
  for(int i=head[x];i;i=edge[i].nex)
  {
    int y=edge[i].to;
    if( !vis[i] )
    {
      vis[i]=vis[i^1]=1;//记录边，这个方向已经确定了
      if( !dfn[y] )
      {tarjan(y);
      low[x]=min(low[x],low[y]);
      }
      else low[x]=min(low[x],dfn[y]);
    }
  }
  if( low[x]==dfn[x] )
    {
      clor[x]=++col;
      while( sta[top]!=x ) clor[ sta[top] ]=col,top--;
      top--;
    }
}

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+12;
int u[N<<2],v[N<<2],n,m,dfn[N],low[N];
int id,cnt=1,f[N],sum,vis[N],head[N];
int sta[N],clor[N],col,top,du[N];
struct {
  int to,nex;
}edge[N<<2];
void addedge(int u,int v)
{
  cnt++;
  edge[cnt]={ v,head[u] };
  head[u]=cnt;
}
void tarjan(int x)
{
  dfn[x]=low[x]=++id;
  sta[++top]=x;
  for(int i=head[x];i;i=edge[i].nex)
  {
    int y=edge[i].to;
    if( !vis[i] )
    {
      vis[i]=vis[i^1]=1;
      if( !dfn[y] )
      {tarjan(y);
      low[x]=min(low[x],low[y]);
      }
      else low[x]=min(low[x],dfn[y]);
    }
  }
  if( low[x]==dfn[x] )
    {
      clor[x]=++col;
      while( sta[top]!=x ) clor[ sta[top] ]=col,top--;
      top--;
    }
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
  {
    scanf("%d%d",&u[i],&v[i]);
    addedge(u[i],v[i]);
    addedge(v[i],u[i]);
  }
  for(int i=1;i<=n;i++)
  {
    if( !dfn[i] )
      tarjan(i);
  }
  for(int i=1;i<=m;i++)
  {
    if( clor[ u[i] ]!=clor[ v[i] ] )
    {
      du[ clor[ u[i] ] ]++;
      du[ clor[ v[i] ] ]++;
    }
  }
    for(int i=1;i<=col;i++)
  {
    if( du[i]==1 ) sum++;
  }
  printf("%d",(sum+1)/2 );
}