POJ 3352 Road Construction

题意：

一个无向图（无重边），问至少还要加多少边使得去掉任意一条边后任意两点仍可互达。

先无向图缩点（就是有向图缩点加一个父亲判断），然后缩完点重新建图，重新建出来的图就是一棵树了

如果只有一个点，那么直接输出0

如果有 \(i\) 个叶子节点，那么就要加 \(i\) 条边，也就是第 \(i\) 个叶子节点向 \(i+1\) 号叶子节点连一条边，\(1\) 号叶子节点向最大标号的叶子节点连边，这样就把所有叶子节点组成了一个环，那么树上所有节点都在这个环内

Wrong Answer

显然，这不是最优的

可以 1 号与 2 号连边，3 号和 4 号连边，\(2i-1\) 向 \(2i\) 连边，如果多出来一条就随便连一个叶子就行

可以用叶子节点的度都为 1（无向图意义的度）来判断是不是叶子节点

答案就是 \(\lfloor \frac {\text{新图叶子节点个数+1}}{2} \rfloor\)

// This code writed by chtholly_micromaker(MicroMaker)
// #include <bits/stdc++.h>  fuck poj
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#define reg register
using namespace std;
const int MaxN=1050;
struct Edge
{
    int nxt,to;
}E[MaxN<<2];
template <class t> inline void read(t &s)
{
    s=0;
    reg int f=1;
    reg char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(isdigit(c))
        s=(s<<3)+(s<<1)+(c^48),c=getchar();
    s*=f;
    return;
}
int hd[MaxN],en,n,m;
int dfn[MaxN],low[MaxN],dep;
int col[MaxN],scc;
int sta[MaxN],top;
bool instack[MaxN];
bool link[MaxN][MaxN];
int deg[MaxN];
inline void adde(int u,int v)
{
    ++en;
    E[en]=(Edge){hd[u],v};
    hd[u]=en;
    return;
}
inline void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++dep;
    sta[top++]=u;
    instack[u]=true;
    for(int i=hd[u];~i;i=E[i].nxt)
    {
        reg int v=E[i].to;
        if(v==fa)
            continue;
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        ++scc;
        do
        {
            --top;
            instack[sta[top]]=false;
            col[sta[top]]=scc;
        }while(u!=sta[top]);
    }
    return;
}
signed main(void)
{
    memset(hd,-1,sizeof hd);
    cin>>n>>m;
    reg int u,v;
    for(int i=1;i<=m;++i)
    {
        read(u);read(v);
        adde(u,v);
        adde(v,u);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            tarjan(i,0);
    if(scc==1)
    {
        puts("0");
        return 0;
    }
    for(int u=1;u<=n;++u)
        for(int i=hd[u];~i;i=E[i].nxt)
        {
            reg int v=E[i].to;
            if(col[u]==col[v])
                continue;
            link[col[u]][col[v]]=true;
        }
    for(int i=1;i<=scc;++i)
        for(int j=1;j<=scc;++j)
            if(link[i][j])
                ++deg[i];
    reg int ans=0;
    for(int i=1;i<=scc;++i)
        if(deg[i]==1)
            ++ans;
    ans=ans/2+(ans&1);
    cout<<ans<<endl;
    return 0;
}

POJ 3352 Road Construction

原文：https://www.cnblogs.com/chinesepikaync/p/12436919.html