8 9
1 2
2 3
3 4
4 2
3 5
5 6
6 7
7 5
7 8

这个应该是1

然而我XJB写的跑出来是2,居然过了
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 10000+10;

struct node
{
    int en;
    bool bridge;
    int next;
}E[N];

int ans;
int top;
int n,m;
int dfs_clock;
int dfn[N];
int low[N];
bool vis[N];
int head[N];
int cntb;

void Init()
{
    ans = 0;
    top = 0;
    dfs_clock = 1;
    for(int i = 0;i < N;i++)
    {
        vis[i] = false;
        head[i] = -1;
        dfn[i] = 0;
        low[i] = 0;
    }
}

void add(int u,int v)
{
    E[top].en = v;
    E[top].bridge = false;
    E[top].next = head[u];
    head[u] = top++;
}

void Find_Bridge(int u,int fa)
{
    dfn[u] = low[u] = dfs_clock++;
    int child = 0;
    for(int i = head[u]; i != -1; i = E[i].next)
    {
        int v = E[i].en;
        if(!dfn[v])
        {
            Find_Bridge(v,u);
            if(low[u] > low[v])
                low[u] = low[v];
            if(low[v] > dfn[u])
                E[i].bridge = true;
        }
        else if(dfn[u] > dfn[v] && v != fa)
            low[u] = min(low[u],dfn[v]);
    }
}

void dfs_bridge(int u,int fa)
{
    int flag = false;
    for(int i = head[u]; i != -1; i = E[i].next)
    {
        if(E[i].bridge && E[i].en != fa)
        {
            E[i].bridge = false;
            flag = true;
            dfs_bridge(E[i].en,u);
        }
    }
    if(!flag)
    {
        //printf("%d  ",u);
        cntb++;
    }
}

void dfs(int u)
{
    vis[u] = true;
    for(int i = head[u]; i != -1; i = E[i].next)
    {
        int v = E[i].en;
        if(!vis[v])
        {
            if(E[i].bridge)
            {
                cntb = 0;
                dfs_bridge(u,-1);
                ans += cntb;
            }
            dfs(v);
        }
    }
}

int main()
{
    int T = 1;
    while(scanf("%d%d",&n,&m) != EOF)
    {
        Init();
        for(int i = 1;i <= m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        Find_Bridge(1,-1);
        dfs(1);
        printf("%d\n",(ans+1)/2);
    }
    return 0;
}

• Re:这个题的数据太弱了吧 (23) w1171689677 2018-09-20 19:36:51