玄关,20分求助
查看原帖
玄关,20分求助
1248282
kpmark楼主2024/8/10 14:55

链式前向星建的图,但是只过了#1,求问问题在哪

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
struct Edge {
    int u, v;
} edge[1000005];

bool cmp(Edge a, Edge b) {
    if (a.v == b.v)
        return a.u > b.u;
    else
        return a.v > b.v;
}

int n, m;
int head[100005], Next[1000005], to[1000005];
int cnt = 1;
int vis[100005];
void add(int x, int y) {
    Next[cnt] = head[x];
    head[x] = cnt;
    to[cnt] = y;
    cnt++;
}

void dfs(int u) {
    if (vis[u])
        return;
    vis[u] = 1;
    cout << u << ' ';
    for (int e = head[u]; e != 0; e = Next[e]) {
        dfs(to[e]);
    }
}

queue<int> q;
void bfs() {
    q.push(1);
    vis[1] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << ' ';
        for (int e = head[u]; e != 0; e = Next[e]) {
            if (vis[to[e]] == 0) {
                q.push(to[e]);
                vis[to[e]] = 1;
            }
        }
    }
}

int main() {
    // 关同步流
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> edge[i].u >> edge[i].v;
    }
    sort(edge + 1, edge + 1 + n, cmp);
    for (int i = 1; i <= m; i++)
        add(edge[i].u, edge[i].v);
    dfs(1);
    cout << endl;
    memset(vis, 0, sizeof(vis));
    bfs();
    return 0;
}
2024/8/10 14:55
加载中...