题面传送门
解决思路
本题解是对 这篇题解 部分内容的补充，讨论的是两种 \(\mathcal{O(m \log n)}\) 的做法。
大体思路都是一样的，先预处理出每一条边需要多少时间后才能连上，可以用 \(\text{BFS}\) 实现。
然后二分答案时间，在每个时间下连接当前已经通的边。设点 \(i\) 第一次被“点燃”的时间为 \(dis_i\)，当前二分的时间为 \(t\)，则 \((u,v)\) 联通的条件是 \(dis_u\le t \text{ and }dis_v\le t\)，然后再新图上判断是否有环即可。
首先是 \(\text{Tarjan}\)。本题数据范围较大，而且 \(\text{Tarjan}\) 常数较大，需要快读 \(+\) 邻接表才能通过。
具体实现就是常规的 \(\text{Tarjan}\)，做完一个点 \(x\) 之后，若 \(low_x<dfn_x\) ，说明它可以通过非树边到达其祖先，也就是存在环了。另外，因为二分答案做多次 \(\text{Tarjan}\)，所以每次要清空！
AC Code（Tarjan）
//If, one day, I finally manage to make my dreams a reality...
//I wonder, will you still be there by my side?
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define y1 cyy
#define fi first
#define se second
#define cnt1(x) __builtin_popcount(x)
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define psi pair<string,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lbt(x) (x&(-x))
using namespace std;
int n,m,k,u[2000005],v[2000005],b,dis[1000005];
int dfn[1000005],low[1000005],timer,head[4000005],tot,Head[1000005],Tot;
int stk[1000005],top,col[1000005];
bool mark[1000005],vis[1000005],fl;
struct node{
int to,nxt;
}e[4000005];
struct NODE{
int to,nxt;
}E[4000005];
queue<int> q;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
char c=gc();int res=0,f=1;
for(;c<'0'||c>'9';c=gc()) if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=gc()) res=res*10+c-'0';
return res*f;
}
inline void write(int x){
static int sta[205],top=0;
if(x<0)putchar('-'),x=-x;
do{sta[top++]=x%10;x/=10;}while(x);
while(top) putchar(sta[--top]+48);
}
inline void writesp(int x){
write(x);putchar(' ');
}
inline void writeln(int x){
write(x);putchar('\n');
}
void add(int u,int v){
e[++tot]={v,head[u]},head[u]=tot;
}
void ADD(int u,int v){
E[++Tot]={v,Head[u]},Head[u]=Tot;
}
void init(){
for(int i=1;i<=m*2;i++) head[i]=0;
for(int i=1;i<=n;i++) dfn[i]=low[i]=col[i]=0,vis[i]=0;
tot=timer=0,fl=0;
}
void tarjan(int x,int fa){
if(fl) return ;
dfn[x]=low[x]=++timer;
for(int i=head[x];i;i=e[i].nxt){
int tmp=e[i].to;
if(tmp==fa) continue;
if(!dfn[tmp]){
tarjan(tmp,x);
if(fl) return ;
low[x]=min(low[x],low[tmp]);
}
else low[x]=min(low[x],dfn[tmp]);
}
if(low[x]<dfn[x]){
fl=1;
return ;
}
}
bool check(int mid){
init();
for(int i=1;i<=m;i++) if(dis[u[i]]<=mid&&dis[v[i]]<=mid){
add(u[i],v[i]),add(v[i],u[i]);
}
for(int i=1;i<=n;i++) if(!dfn[i]) top=0,tarjan(i,0);
return fl;
}
signed main(){
n=read(),m=read(),k=read();
for(int i=1;i<=m;i++){
u[i]=read(),v[i]=read();
ADD(u[i],v[i]),ADD(v[i],u[i]);
}
for(int i=1;i<=n;i++) dis[i]=1e9;
for(int i=1;i<=k;i++) b=read(),q.push(b),dis[b]=0;
while(q.size()){
int x=q.front();q.pop();
vis[x]=1;
for(int i=Head[x];i;i=E[i].nxt){
int tmp=E[i].to;
if(vis[tmp]) continue;
if(dis[tmp]>dis[x]+1){
dis[tmp]=dis[x]+1;
q.push(tmp);
}
}
}
int l=0,r=n,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
if(ans==-1) puts("Poor D!");
else writeln(ans);
return 0;
}
然后是并查集。并查集在本题中简单很多，而且效率也更高。具体实现就是依次判断每条边，如可以连接的两点已经在同一个连通块中了，就说明有环，否则就连上。同样注意要清空。
AC Code（DSU）
//If, one day, I finally manage to make my dreams a reality...
//I wonder, will you still be there by my side?
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define y1 cyy
#define fi first
#define se second
#define cnt1(x) __builtin_popcount(x)
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define psi pair<string,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lbt(x) (x&(-x))
using namespace std;
int n,m,k,u[2000005],v[2000005],b,dis[1000005];
int Head[1000005],Tot;
bool vis[1000005];
struct DSU{
int fa[1000005];
void init(int n){
for(int i=1;i<=n;i++) fa[i]=i;
}
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y){
fa[find(x)]=find(y);
}
bool query(int x,int y){
return find(x)==find(y);
}
}dsu;
struct NODE{
int to,nxt;
}E[4000005];
queue<int> q;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
char c=gc();int res=0,f=1;
for(;c<'0'||c>'9';c=gc()) if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=gc()) res=res*10+c-'0';
return res*f;
}
inline void write(int x){
static int sta[205],top=0;
if(x<0)putchar('-'),x=-x;
do{sta[top++]=x%10;x/=10;}while(x);
while(top) putchar(sta[--top]+48);
}
inline void writesp(int x){
write(x);putchar(' ');
}
inline void writeln(int x){
write(x);putchar('\n');
}
void ADD(int u,int v){
E[++Tot]={v,Head[u]},Head[u]=Tot;
}
bool check(int mid){
dsu.init(n);
for(int i=1;i<=m;i++) if(dis[u[i]]<=mid&&dis[v[i]]<=mid){
if(dsu.query(u[i],v[i])) return 1;
else dsu.merge(u[i],v[i]);
}
return 0;
}
signed main(){
n=read(),m=read(),k=read();
for(int i=1;i<=m;i++){
u[i]=read(),v[i]=read();
ADD(u[i],v[i]),ADD(v[i],u[i]);
}
for(int i=1;i<=n;i++) dis[i]=1e9;
for(int i=1;i<=k;i++) b=read(),q.push(b),dis[b]=0;
while(q.size()){
int x=q.front();q.pop();
vis[x]=1;
for(int i=Head[x];i;i=E[i].nxt){
int tmp=E[i].to;
if(vis[tmp]) continue;
if(dis[tmp]>dis[x]+1){
dis[tmp]=dis[x]+1;
q.push(tmp);
}
}
}
int l=0,r=n,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
if(ans==-1) puts("Poor D!");
else writeln(ans);
return 0;
}