プログラマの最も遠いノード

質問する

コード#コード#

#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<pair<int, int>>> graph(n+1);
    priority_queue<pair<int, int>> pq;
    vector<int> table(n+1,1e9);

    for (auto i : edge){
        graph[i[0]].push_back({1, i[1]});
        graph[i[1]].push_back({1, i[0]});
    }

    pq.push({ 0,1 });
    table[1] = 0;
    int maxN = 0;
    while (!pq.empty()){
        int d = -pq.top().first;
        int num = pq.top().second;
        pq.pop();

        if (table[num] < d) continue;

        for (int i = 0; i < graph[num].size(); i++){
            int cost = d + graph[num][i].first;

            if (cost < table[graph[num][i].second]){
                table[graph[num][i].second] = cost;
                pq.push({-cost, graph[num][i].second});
                maxN = max(maxN, cost);
            }
        }
    }
    for (int i : table){
        if (i == maxN)
            answer++;
    }
    return answer;
}

に答える

隣接マトリクスコード

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    int maxValue=0;
    vector<vector<int>> graph(n,vector<int>(n,0));
    for(auto i:edge){
        graph[i[0]-1][i[1]-1]=-1;
        graph[i[1]-1][i[0]-1]=-1;
    }
    for(int i=0;i<n;i++) graph[i][i]=-1;
    
    queue<vector<int>> q;
    q.push({0,0,1});
    while(!q.empty()){
        int y=q.front()[0];
        int x=q.front()[1];
        int dist=q.front()[2];
        maxValue=max(maxValue,dist);
        q.pop();
        
        for(int i=0;i<n;i++){
            if(graph[y][i]==-1){
                graph[y][i]=dist;
                q.push({y,i,dist+1});
            }
            if(graph[i][x]==-1){
                graph[i][x]=dist;
                q.push({i,x,dist+1});
            }
        }  
    }

    for(int i=0;i<n;i++){
        if(graph[i][i]==maxValue-1)answer++;
    }
    return answer;
}