cf1000E We Need More Bosses (tarjan缩点+树的直径)

题意:无向联通图,求一条最长的路径,路径长度定义为u到v必须经过的边的个数

如果把强联通分量都缩成一个点以后,每个点内部的边都是可替代的;而又因为这是个无向图,缩完点以后就是棵树,跑两遍dfs求直径即可

 #include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=3e5+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int eg[maxn*][],egh[maxn],ect;
int eg2[maxn*][],egh2[maxn],ect2;
int N,M,dfn[maxn],tot,low[maxn],stk[maxn],sh,bel[maxn];
int ma,xx;
bool instk[maxn]; inline void adeg(int a,int b){
eg[++ect][]=b,eg[ect][]=egh[a],egh[a]=ect;
}
inline void adeg2(int a,int b){
eg2[++ect2][]=b,eg2[ect2][]=egh2[a],egh2[a]=ect2;
} void tarjan(int x,int f){
dfn[x]=low[x]=++tot;instk[x]=;stk[++sh]=x;
for(int i=egh[x];i;i=eg[i][]){
int b=eg[i][];if(b==f) continue;
if(!dfn[b]) tarjan(b,x),low[x]=min(low[x],low[b]);
else if(instk[b]) low[x]=min(low[x],dfn[b]);
}
if(dfn[x]==low[x]){
while(){
bel[stk[sh]]=x,instk[stk[sh]]=;
if(stk[sh--]==x) break;
}
}
} void dfs(int x,int f,int dis){
if(dis>ma) ma=dis,xx=x;
for(int i=egh2[x];i;i=eg2[i][]){
int b=eg2[i][];
if(b==f) continue;
dfs(b,x,dis+);
}
} int main(){
int i,j,k;
N=rd(),M=rd();
for(i=;i<=M;i++){
int a=rd(),b=rd();
adeg(a,b);adeg(b,a);
}
tarjan(,);
for(i=;i<=N;i++){
for(j=egh[i];j;j=eg[j][]){
int b=eg[j][];
if(bel[i]==bel[b]) continue;
adeg2(bel[i],bel[b]);
}
}
ma=;xx=bel[];
dfs(bel[],,);
dfs(xx,,);
printf("%d\n",ma);
return ;
}
上一篇:洛谷 P2218 [HAOI2007]覆盖问题 解题报告


下一篇:用SignalR 2.0开发客服系统[系列5:使用SignalR的中文简体语言包和其他技术点]