【ZJOI2004】嗅探器

描述
某军搞信息对抗实战演习.红军成功地侵入了蓝军的内部网络.蓝军共有两个信息中心.红军计划在某台中间服务器上安装一个嗅探器,从而能够侦听到两个信息中心互相交换的所有信息.但是蓝军的网络相当的庞大,数据包从一个信息中心传到另一个信息中心可以不止有一条通路.现在需要你尽快地解决这个问题.应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获?


输入
第一行一个整数n(1<=n<=100),表示蓝军网络中服务器的数目.


接下来若干行是对蓝军网络的拓扑结构描述.每行是两个整数i,j表示编号为I和编号为j的两台服务器间存在连接(显然连接是双向的).


服务器的编号从1开始.描述一两个0结束.再接下来一行是两个整数a,b分别表示两个中心服务器的编号


.如果有多个解输出编号最小的一个.


如果找不到任何解,输出”No solution”.


输出
样例输入 
5
2 1
2 5
1 4
5 3
2 3
5 1
0 0
4 2
样例输出 

1

分析：tarjan的应用。按照题意，一定满足：要求的点是割点，但割点不一定满足要求。所以，取两个点中的一个点为根，算出割点，再check割点是否满足条件，

#include<bits/stdc++.h>
using namespace std;

#define N 1001
#define MAXN  0x7fffffff

int n,p,r,a,b,root,cnt,cot,ans=MAXN;
int first[N],dfn[N],low[N],pri[N];

struct email
{
    int u,v;
    int nxt;
}e[N*100];

void add(int u,int v)
{
    e[++cnt].nxt=first[u];first[u]=cnt;
    e[cnt].u=u;e[cnt].v=v;
}

void dfs(int u,int fa)
{
    int son=0;
    dfn[u]=low[u]=++cot;
    for(int i=first[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(dfn[v]==0)
        {
            pri[v]=u;
            dfs(v,u);
            low[u]=min(low[u],low[v]);
        }
        else
            if(v!=fa)
                low[u]=min(low[u],dfn[v]);    
    }    
}

void init()
{
    cnt=0;cot=0;
    memset(first,0,sizeof(first));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(pri,0,sizeof(pri));
}

void readin()
{
    scanf("%d",&n);
    while(1)
    {
        scanf("%d%d",&p,&r);
        if(p==0&&r==0)
            break;    
        add(p,r);add(r,p);
    }
    scanf("%d%d",&a,&b);
}

void check(int t)
{
    if(t==root)    return;
    if(low[t]>=dfn[pri[t]]&&pri[t]!=root&&pri[t]<ans)//从b点倒着搜到a，保留dfn最小的值
        ans=pri[t];    
    check(pri[t]);
}

int main()
{    
    init();
    readin();
    root=a;
    dfs(root,-1);
    check(b);    
    if(ans<MAXN)
        printf("%d",ans);
    else
        printf("No solution");
    return 0;
}