hdu-4612-强连通分量

题意：

有一些小岛，这些小岛上有一些边，让你加一条边，使得原先的那些边的桥数最少。

做法：
1，把小岛为点，连接小岛的为边建图。

2，求出图中的所有强联通分量

3，把所有的强联通分量看成一个点建树。

4，求树的直径，新加的那条边应该在直径的两边，这样才能使得图中的桥最小。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
using namespace std;
#define maxn 200003
#define mem(a,b) memset(a,b,sizeof(a))
vector<int>q[maxn];
stack<int>qq;
struct list
{
    int e;
    int next;
}edge[maxn*10];
struct ll
{
    int u;
    int v;
}node[maxn*5];
int tops,times,nums,n,m;
int dnf[maxn];
int low[maxn];
int instack[maxn];
int head[maxn*10];
int vis[maxn*10];
int dist[maxn];
int num[maxn];
int visit[maxn];
void add(int x,int y)
{
    edge[tops].e=y;
    edge[tops].next=head[x];
    head[x]=tops++;
}
void tarjan(int x)
{
    dnf[x]=low[x]=times++;
    instack[x]=1;
    qq.push(x);
    for(int i=head[x];i!=-1;i=edge[i].next)
    {
        int y=edge[i].e;
        if(vis[i])continue;
        vis[i]=vis[i^1]=1;
        if(!dnf[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(instack[y])
        {
            low[x]=min(low[x],dnf[y]);
        }
    }
    if(low[x]==dnf[x])
    {
        int y=-1;
        while(x!=y)
        {
            y=qq.top();
            qq.pop();
            instack[y]=0;
            num[y]=nums;
        }
        nums++;
    }
}
int spfa(int x)
{
    for(int i=0;i<=nums;i++)
    {
        dist[i]=-1;
        visit[i]=0;
    }
    queue<int>pp;
    pp.push(x);
    dist[x]=0;
    visit[x]=1;
    while(!pp.empty())
    {
        int y=pp.front();
        pp.pop();
        for(int i=0;i<q[y].size();i++)
        {
            int z=q[y][i];
            if(!visit[z])
            {
                dist[z]=dist[y]+1;
                visit[z]=1;
                pp.push(z);
            }
        }

    }
    int maxx,ip;
    maxx=-1;
    for(int i=0;i<nums;i++)
    {
        if(dist[i]>maxx)
        {
            maxx=dist[i];
            ip=i;
        }
    }
    return ip;
}
int main()
{
    int a,b,i;
    while(scanf("%d%d",&n,&m)&&(n||m))
    {
        tops=0;
        times=1;
        nums=0;
        for(i=0;i<=m*2;i++)
        {
            vis[i]=0;
            head[i]=-1;
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
            node[i].u=a;
            node[i].v=b;
        }
        for(i=0;i<=n;i++)dnf[i]=low[i]=instack[i]=0;
        while(!qq.empty())qq.pop();
        for(i=1;i<=n;i++)
            if(!dnf[i])tarjan(i);
        tops=0;
        for(i=0;i<=nums;i++)q[i].clear();
        for(i=0;i<m;i++)
        {
            if(num[node[i].u]!=num[node[i].v])
            {
                q[num[node[i].u]].push_back(num[node[i].v]);
                q[num[node[i].v]].push_back(num[node[i].u]);
            }
        }
        printf("%d\n",nums-dist[spfa(spfa(0))]-1);
    }
    return 0;
}

补充：软件开发 , C++ ,