도 론 - 최소 생 성 트 리 Boruvka

Boruvka 알고리즘 은 알고리즘 사상 이 욕심 이 고 Kruskal 과 유사 합 니 다.
처음 상 태 는 점 마다 하나의 단독 연결 블록 이 었 다.모든 점 과 변 을 옮 겨 다 니 며 모든 연결 블록 과 다른 연결 블록 이 연 결 된 가장 작은 변 을 찾 은 다음 에 연결 블록 을 합 쳐 하나의 연결 블록 만 남 을 때 까지 상기 작업 을 반복 합 니 다.
매번 두 개의 연결 블록 을 합 쳐 전체 프로그램 이 log 회 작업 을 하면 완 성 됩 니 다. 매번 작업 의 복잡 도 는 n + m 이 고 복잡 도 는 O (n + m) logn 입 니 다.https://www.luogu.org/problemnew/show/P3366 코드 는 다음 과 같 습 니 다:

#include 
#include 
#include 
using namespace std;
int pre[400001],other[100001],last[5001],l,len[400001];
int n,m;
void add(int x,int y,int z)
{
    ++l,pre[l]=last[x],last[x]=l,other[l]=y,len[l]=z;
}
int f[5001],mn[2][5001];
int findd(int x)
{
    return x==f[x]?x:f[x]=findd(f[x]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i) f[i]=i;
    for (int i=1,x,y,z;i<=m;++i) scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z); 
    int ans=0;
    while(1)
    {
        memset(mn[0],127,sizeof mn[0]);
        bool flag=0;
        for (int i=1;i<=n;++i)
            for (int p=last[i];p;p=pre[p])
                if (findd(i)!=findd(other[p])&&mn[0][findd(i)]>len[p]) mn[0][findd(i)]=len[p],mn[1][findd(i)]=findd(other[p]);
        for (int i=1;i<=n;++i)
            if (mn[0][i]!=mn[0][0]&&findd(i)!=findd(mn[1][i])) flag=1,ans+=mn[0][i],f[f[i]]=f[mn[1][i]];
        if (!flag) break;
    }
    for (int i=1;i<n;++i)
    	if (findd(i)!=findd(i+1))
   	 	{
   	    	puts("orz");
   	     	return 0;
    	}   
    cout<<ans;
}