@[2002chenhan](/space/show?uid=31585) 这个题怎么会不连通呢？你是先跑完了最大生成树，那么，这棵树上的每一个点都是联通的啊
by AugustQ @ 2018-11-06 19:11:42
```cpp
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=10010,MAXM=50010;
struct E{int x,y,z,next;}ed[MAXM*2]; int last[MAXN],len,n;
struct Ed{int x,y,z;}ed1[MAXM]; int len1;
int fa[MAXN],dep[MAXN],f[MAXN][25],d[MAXN][25];
void inss(int x,int y,int z) { ed1[++len1]=(Ed){x,y,z}; }
void ins(int x,int y,int z) { ed[++len]=(E){x,y,z,last[x]}; last[x]=len; }
bool cmp(Ed x,Ed y) { return x.z>y.z; }
int find_fa(int x) { return fa[x]==x?x:fa[x]=find_fa(fa[x]); }
void Kruskal()
{
int cnt=0;
for(int k=1;k<=len1;k++)
{
int x=ed1[k].x,y=ed1[k].y;
int a=find_fa(x),b=find_fa(y);
if(a!=b)
{
fa[a]=b;
ins(x,y,ed1[k].z);
ins(y,x,ed1[k].z);
cnt++;
if(cnt==n-1) return ;
}
}
}
void Pre(int x,int fa)
{
for(int k=last[x];k;k=ed[k].next)
{
int y=ed[k].y;
if(y!=fa)
{
if(dep[y]) continue;
dep[y]=dep[x]+1;
f[y][0]=x;
d[y][0]=ed[k].z;
for(int i=1;i<=20;i++) f[y][i]=f[f[y][i-1]][i-1];
for(int i=1;i<=20;i++)
d[y][i]=min(d[y][i-1],d[f[y][i-1]][i-1]);
Pre(y,x);
}
}
}
int LCA(int x,int y)
{
int re=0x3f3f3f3f;
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;i--) if(dep[f[x][i]]>=dep[y]) re=min(re,d[x][i]),x=f[x][i];
if(x==y) return re;
for(int i=20;i>=0;i--) if(f[x][i]!=f[y][i]) re=min(re,min(d[x][i],d[y][i])),x=f[x][i],y=f[y][i];
if(f[x][0]==f[y][0]) return min(re,min(d[x][0],d[y][0]));
return 0x3f3f3f3f;//////看这看这看这看这看这看这看这看这看这
}
int main()
{
int m,x,y,z;
scanf("%d%d",&n,&m);
memset(d,63,sizeof(d));
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
inss(x,y,z);
}
sort(ed1+1,ed1+len1+1,cmp);
for(int i=1;i<=n;i++) fa[i]=i;
Kruskal();
for(int i=1;i<=n;i++) if(!dep[i]) Pre(i,0);
int Q; scanf("%d",&Q);
while(Q--)
{
scanf("%d%d",&x,&y);
int ans=LCA(x,y);
if(ans!=0x3f3f3f3f) printf("%d\n",ans);
else puts("-1");
}
return 0;
}
```
就是这样不用并查集，用lca来判，结果只有85分
by 2002chenhan @ 2018-11-06 19:22:45
@[Loi_zrq](/space/show?uid=61264)
by 2002chenhan @ 2018-11-06 19:22:59
@[2002chenhan](/space/show?uid=31585) 我给你加上判断是否为同一祖先就A了。
```cpp
while(Q--)
{
scanf("%d%d",&x,&y);
int ans=LCA(x,y),fx=find_fa(x),fy=find_fa(y);
if(fx!=fy)puts("-1");
else printf("%d\n",ans);
}
```
就是这里
by AugustQ @ 2018-11-06 19:43:32
但为什么你原来的不对，我还没看出来。再给我点时间....
by AugustQ @ 2018-11-06 19:44:11
是的，并查集是可以过的
by 2002chenhan @ 2018-11-06 19:53:58
@[Loi_zrq](/space/show?uid=61264) 这个图有n个点，m条边，m可能<n-1，所以可能不连通
by 2002chenhan @ 2018-11-06 21:55:02