3352.cpp

poj3352给一个图,求出需要加最少的边使去掉任一条边,图都连通.割点的应用

#include <iostream>
using namespace std;
typedef struct node
{
    int u,next;
}node;
#define MAXK   2000
#define MAXN   1000
typedef struct lnode
{
	int l,k;
}lnode;

node link[MAXK];
int g[MAXN];
int n,r,i,ans,x;
int top;
lnode l[MAXN];

void insert(int a,int b)
{
    int p;
    
    p = ++top;
    link[p].next = g[a];
    link[p].u = b;
    g[a] = p;
}

void init()
{
    int i,a,b;
    
    cin>>n>>r;
    for (i=0 ;i<n ;i++)
    {
        g[i] = -1;
        l[i].l = l[i].k = 0;
    }
    ans = 0;
    top = -1;
    for (i=0 ;i<r ;i++)   
    {
        cin>>a>>b;
        insert(a-1,b-1);
        insert(b-1,a-1);
    }
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

void dfs(int v,int f)
{
    int u,t,tc;
    int d = 0;

    i++;
    l[v].l = l[v].k = i;
    t = g[v];
    while (t!=-1)
    {
		d++;
        u = link[t].u;
        if (l[u].l == 0)
        {
			tc = ans;
            dfs(u,v);
            l[v].l = min(l[v].l,l[u].l);
            if (l[u].l > l[v].k && tc == ans)
				ans++;             
        }
		else if (u!=f)
		{
			l[v].l = min(l[v].l,l[u].l);
		}
        t = link[t].next;
    } 
	if (d == 1) ans++;
}                             

void work()
{
    i = 0;
    dfs(0,-1);
    cout<<(ans+1)/2<<endl;
}        
int main()
{
    init();
    work();
    return 0;
}