ネストしたデータ構造のSTLソート

Question

これはC++でグラフを表現するために作成したSTLベースのデータ構造です。私は彼がエッジのベクトルを使用していますスティーブン・ハリムさん（競争プログラミング）の本で読んクラスカルのアルゴリズムで

typedef std::pair<int,int> ii; 
typedef std::vector<ii> vii; 
typedef std::vector<vii> graph; 

。

vector< pair<int, pair<int,int> > > edges; 

その後、彼はソートは、重量（ペアの最初のint型）です。私はこのアルゴリズムを実装していましたが、以前のデータ構造を使いたいので、ネストされた構造を持っているので、ウェイトでソートする方法がわかりません。

vector< vector< pair < int, int> > > graph - このグラフを重みを表すペアで2番目のパラメータでソートするにはどうすればよいですか？

std::sort(mygraph.begin(), mygraph.end(), /* HERE I GOT A TROUBLE */) 

あなただけのグラフあなたがstd::sort()を使用して望むように並べ替えることはできませんあなた

Answer 1

ありがとうございます。

私が正しく理解していれば、mygraph[u]は重量wのvからuからエッジが存在するように{v,w}ペアが含まれています。あなたはKruskalのための重みでエッジリストをソートしたいと思う。しかし、あなたは単に提案された構造でこれを行うことはできません！

std::sort()オンmygraphは、行の中でエッジを並べることなく隣接リストの行を並べ替えます。最小の辺が異なる行にある可能性があるため、行自体を順序付ける自然な方法はありません。例えば

、このようなベクトルの2つの行を考えてみます。

mygraph[0] = {{1,1}, {3,3}} 
mygraph[1] = {{2,2}} 

は今、あなたはソート順に他の二つの端の間に来て{2,2}エッジをしたいが、あなただけのベクトルを並べ替える場合、これは不可能です。

このようにベクトルを平坦化して、1次元のベクトル（形式：{w,{u,v}}、ハリムの形）を並べ替えることができます。