嗅探器

题目描述：

红蓝军队打演习，蓝军有两个信息中心，红军计划在某个中间服务器上安装一个嗅探器，来获得蓝军情报，而蓝军网络相当庞大，数据包从一个信息中心传到另一个信息中心不止一条路，你需要将嗅探器安装到哪个中间服务器才能保证所有数据包都能被捕获

思路：

转换一下其实是找割点，但不仅仅是割点，是能将两个信息中心隔开的割点，只有割点才能将这两个信息中心隔断，不能进行信息交流，但如果判断这个割点能否将这两个信息中心隔断呢？

我们以其中一个数据中心a为起点使用tarjan，如果遇到了割点，就说明这个割点的dfn值一定大于等于a，此时判断一下这个割点是不是a或b，如果不是，且dfn[b] >= dfn[u], low[b] >= dfn[u]，u是tarjan传参量，意思是数据中心b的在u的后面，且b无法通过low回到比u小的地方，而因为是从a开始跑的，且前面判了u不等于a ，也就是此时a在u上面，这样u就将a和b隔断开了，当然dfn[b] >= dfn[u], low[b] >= dfn[u]可以缩写成low[b] >= dfn[u]，因为dfn永远大于等于low，当一个小的数大于u，那比他大的数也一定大于u

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1.0E-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  2000000 + 50
//#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define max(a,b) (((a)>(b)) ? (a):(b))
#define min(a,b) (((a)>(b)) ? (b):(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, a, b, ans;

int tot;
int head[MAX];
struct ran{
    int to, nex;
}tr[MAX];
void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int tim;
int dfn[MAX], low[MAX];
void tarjan(int u){
    dfn[u] = low[u] = ++tim;
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if(u != a && u != b && dfn[u] <= low[b] && dfn[u] <= low[v]){
                ans = min(ans, u);
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}


int main(){
    ans = inf;
    sd(n);
    while (sdd(a, b) && (a + b)) {
        add(a, b);
        add(b, a);
    }
    sdd(a, b);
    tarjan(a);
    if(ans == inf)cout<<"No solution\n";
    else cout<<ans<<endl;
    return 0;
}