代码比较丑……

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>

const int maxN = 5010;
struct Edge
{
    int v; bool bridge;
    Edge *next, *back; Edge() {}
    Edge(int v, Edge *next):
        v(v), next(next), bridge(0) {}
} *edge[maxN], *bridge[maxN];
bool marked[maxN];
int DFN[maxN], Low[maxN], stack[maxN];
int Belong[maxN], Degree[maxN];
int root, Dcnt, Ind, leaf, top, n, m;

inline int getint()
{
    int res = 0; char tmp;
    while (!isdigit(tmp = getchar()));
    do res = (res << 3) + (res << 1) + tmp - '0';
    while (isdigit(tmp = getchar()));
    return res;
}

void tarjan(int u, int Last)
{
    DFN[u] = Low[u] = ++Ind;
    marked[stack[++top] = u] = 1;
    for (Edge *p = edge[u]; p; p = p -> next)
    if (p -> v != Last)
//这样每次判断不等于父亲好像在有重边的情况下要错
    {
        int v = p -> v;
        if (!DFN[v])
        {
            tarjan(v, u);
            Low[u] = std::min(Low[u], Low[v]);
            if (DFN[u] < Low[v])
            {
                p -> back -> bridge = p -> bridge = 1;
//标记为桥。
                ++Dcnt; int tmp = v;
                do
                {
                    tmp = stack[top--];
                    marked[tmp] = 0;
                    Belong[tmp] = Dcnt;
                } while (tmp - v);
            }
        }
        else if (marked[v])
            Low[u] = std::min(Low[u], DFN[v]);
    }
    return;
}

int main()
{
    freopen("Redundant_Paths.in", "r", stdin);
    freopen("Redundant_Paths.out", "w", stdout);
    n = getint(); m = getint();
    while (m--)
    {
        int u = getint(), v = getint();
        edge[u] = new Edge(v, edge[u]);
        edge[v] = new Edge(u, edge[v]);
        edge[u] -> back = edge[v];
        edge[v] -> back = edge[u];
    }
    tarjan(1, -1); int tmp = 1; ++Dcnt;
    do
    {
        tmp = stack[top--];
        marked[tmp] = 0;
        Belong[tmp] = Dcnt;
    } while (tmp - 1);
//最后把根所在的双联通分量取出来。
    for (int u = 1; u < n + 1; ++u)
    for (Edge *p = edge[u]; p; p = p -> next)
    if (p -> bridge)
//这句要是改成if (Belong[u]!=Belong[p->v])就WA了……
    {
        int v = p -> v;
        bridge[Belong[u]] = new
            Edge(Belong[v], bridge[Belong[u]]);
    }
    int leaf = 0;
    for (int u = 1; u < Dcnt + 1; ++u)
    {
        for (Edge *p = bridge[u]; p; p = p -> next)
            ++Degree[u];
        if (Degree[u] == 1) ++leaf;
    }
    printf("%d\n", leaf == 1 ? 0 : (leaf + 1 >> 1));
    return 0;
}

比如这组数据：
5 23
1 2
5 4
4 1
4 3
5 3
1 5
4 1
3 1
3 1
1 3
4 5
1 2
4 5
3 5
4 5
1 4
3 5
4 5
5 1
4 5
2 1
1 4
5 4
正确答案是0，但我的程序输出1。

• Re:为啥我的程序能过啊？ (2952) Stabber_dove 2016-09-12 16:59:55