MLE#28求助awa
查看原帖
MLE#28求助awa
246331
cat_lover1楼主2024/9/14 01:01
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
const int N=3e5+10;
int n,m,bel[N],vis[N],dfn[N],low[N],stk[N],tp,viss[N],cnt,bcnt; 
int head[N],tot=1; struct {int to,nex;} G[N*2];
void add(int u,int v){
  G[++tot]={v,head[u]},head[u]=tot;
  G[++tot]={u,head[v]},head[v]=tot;
}
vector<int> H[N];
void tarjan(int u){
  dfn[u]=low[u]=++cnt,viss[stk[++tp]=u]=1;
  for(int i=head[u],v=G[i].to;i;i=G[i].nex,v=G[i].to) 
    if(!vis[i]){
      vis[i]=vis[i^1]=1; 
      if(!dfn[v])
        tarjan(v),
        low[u]=min(low[u],low[v]);
      else if(viss[v]) 
        low[u]=min(low[u],dfn[v]);
    }
  if(low[u]!=dfn[u]) return;
  ++bcnt;
  while(stk[tp]!=u){
    bel[stk[tp]]=bcnt;
    viss[stk[tp--]]=0;
  }
  bel[stk[tp]]=bcnt;
  viss[stk[tp--]]=0;
}
int C,dis[N];
void dfs(int u,int fa){
  for(int v:H[u]) if(v^fa)
    dis[v]=dis[u]+1,dfs(v,u);
}
int hsh(int u,int v){
  return u*v+u+v+1;
}
__gnu_pbds::cc_hash_table<long long,bool> Vis;
main(){
  cin.tie(0)->sync_with_stdio(0);
  cin>>n>>m;
  for(int u,v;m--;) cin>>u>>v,add(u,v);
  tarjan(1);
  //int st=0;
  for(int i=1;i<=n;++i) 
    for(int j=head[i],v=G[j].to;j;j=G[j].nex,v=G[j].to)
      if(bel[i]!=bel[v]&&Vis.find(hsh(bel[i],bel[v]))==Vis.end()) 
        Vis[hsh(bel[i],bel[v])]=1,H[bel[i]].push_back(bel[v]),H[bel[v]].push_back(bel[i]);
  dfs(1,0);
  C=max_element(dis,dis+n+1)-dis;
  fill(dis,dis+n+1,0);
  dfs(C,0);
  cout<<*max_element(dis,dis+n+1);
}
2024/9/14 01:01
加载中...