[Programmers]電力網を2つの部分に分けて無秩序set、BFS

3078 ワード
BFS programmers アルゴリズム#アルゴリズム# unordered_set テキストリンク
電力網を二つに分ける

プログラマーの問題は久しぶりです.プログラマの利点は、入力値に関心を持つ必要がないことですが、欠点もあります.
それも正解!においがする.

学識

  • 無秩序set(地図も同様)では、インデックスを使用してアクセスできません.したがって、for文を回転させる場合は、iterを作成するか、for(auto i:set)フォーマットを使用する必要があります.また,挿入はinsert,削除はerase(value)である.
  • absのライブラリはcmathであり,minのライブラリはアルゴリズムである.
  • ノードの値は最大100であるため、すべての幹線を暴力的に比較することができる.与えられた制限条件をよく見てください.
    • #include <string>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define MAXN (100+2)
unordered_set<int>ss[MAXN];
int bfs(int wire){
    int check[MAXN]={0,};
    int cnt=0;
    queue<int>que;
    que.push(wire);
    check[wire]=1;
    while(!que.empty()){
        int data=que.front(); que.pop();
        for(auto next:ss[data]){
            if(check[next]) continue;
            check[next]=1;
            que.push(next);
            cnt++;
        }
    }
    return cnt;
}

int solution(int n, vector<vector<int>> wires) {
    
    int answer = 0x7fffffff;
    for(int i=0;i<wires.size();i++){
        ss[wires[i][0]].insert(wires[i][1]);
        ss[wires[i][1]].insert(wires[i][0]);//양방향 간선
    }//노드간 연결
   
    for(auto wire:wires){
        ss[wire[0]].erase(wire[1]);
        ss[wire[1]].erase(wire[0]);
        
        answer=min(answer, abs(bfs(wire[0])-bfs(wire[1])));
        
        ss[wire[0]].insert(wire[1]);
        ss[wire[1]].insert(wire[0]);
    }
    return answer;
}
    常用cssスタイル(1)
    AngularJSパッケージUuditor