求助此存图方式如何判断联通(用dfs)

P3366 【模板】最小生成树

lwx20211103 @ 2023-07-03 22:48:55


#include <bits/stdc++.h>
using namespace std;

struct graph
{
    int u, v, c;
} gra[214514];

int fa[214514], tot, sum;
int n, m;

bool cmp(graph a, graph b)
{
    return a.c < b.c;
}

int _find(int x)
{
    return (x == fa[x] ? x : fa[x] = _find(fa[x]));
}

void _merge(int u, int v)
{
    int x = _find(u), y = _find(v);
    if (x != y)
        fa[x] = y;
}

void kru()
{   
    for (int i = 1; i <= m; i++)
    {
        int a = _find(gra[i].u), b = _find(gra[i].v);
        if (a == b) continue;
        _merge(a, b);
        sum += gra[i].c;
        tot++;
        if (tot == n - 1) return;
    }   
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        gra[i].u = u, gra[i].v = v, gra[i].c = c;
    }
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
    sort(gra + 1, gra + 1 + m, cmp);
    kru();
    cout << sum;
    return 0;
}

结构体遍历图懵逼中。


by SnapYust @ 2023-07-03 22:57:03

@lwx20211103 卷题佬


by SnapYust @ 2023-07-03 23:01:25

@lwx20211103 用一个变量来存边的数量,每合并一次就++,当算完以后变量还是小于 n-1,那就输出orz


by SnapYust @ 2023-07-03 23:02:04

@lwx20211103

for (int i = 1; i <= m; i++)
    {
        if (Union (e[i].u, e[i].v))
        {
            ans += e[i].w;
            cnt++;
            if (cnt == n - 1)
            {
                cout << ans;
                return 0;
            }
        }
    }
    cout << "orz" << endl;
    return 0;

by lwx20211103 @ 2023-07-04 12:35:45

@SnapYust 你是不是没有看到标题(


by toolazy @ 2023-08-07 19:57:21

并查集吧,最方便了,正好Kruskal也会用到并查集,最后查一下是不是所有节点都是同一个根(蒟蒻别打qwq


|