[CF732F]Tourist Reform

Tourist Reform

题解

很容易发现，对于任意一个边双连通分量，一定存在一种方法使得这个连通分量内的任意两点可以互相到达。

于是将连通分量缩点后我们得到了一棵树，因为总共只有条边，所以必定有一个连通分量无法到达其它的连通分量，而若将它作为树的根，将所有的儿子连向它的父亲，则其余点一定可以到达它，其价值一定比它大。为了使最小价值最大，我们需要选取整体价值最大的一个连通作为根。

由于tarjan算法是一个dfs式的结构，在一个连通分量内我们如果重新到达了一个点，一定是形成了一个环，将环接上即可保证这个边双连通分量将转化为一个连通分量。

所以，我们只要通过dfs反向构造一个环即可。

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 400005
typedef long long LL;
typedef unsigned long long uLL;
const LL mo=1e9+7;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>