白駿2458キー順

問題の説明

方法

まずこれがグラフの問題であることを明確に知り、どうアプローチすればいいのか悩み、複雑に見えるが、一つのアイデアを思いついた.すべての頂点間の関係や距離を探索しながら更新を行い,最終的に更新が完了すると,自分以外のすべての頂点と関係のある頂点とが順序を知ることができ,一つの頂点であっても関係性が空の頂点があれば順序を知らない頂点となる.もちろん、コアはどのように関係性を更新するかです.
図形はキーの大きさ関係として有向図が与えられているが,度,出度で両側に移動すると,図形の情報さえあればよい.では、すべての頂点で1回探索を行い、度方向に隣接する頂点間の関係性のみを見て、度方向に後の頂点まで探索し、再び関係性を更新するように近づく.DFSによる近接が懸念されているが,到達した頂点のチェックはできないが,すべての頂点が大小関係であるため,周期が発生せず,その関係性を探索し更新し続けることが核心である.

主C++コード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair <ll, ll>;

vector<vector<int>> relation;
vector<vector<int>> Bigger;
vector<vector<int>> Smaller;

void DFS(int cur, int diff, int org){
  relation[cur][org] = max(relation[cur][org], diff);
  relation[org][cur] = max(relation[org][cur], diff);

  for(int next : Smaller[cur])
    DFS(next, diff+1, org);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  //freopen("inp.txt", "r", stdin);
  
  int v, e;
  cin >> v >> e;
  relation.resize(v+1, vector<int>(v+1, 0));
  Bigger.resize(v+1);
  Smaller.resize(v+1);

  while(e--){
    int small, big;
    cin >> small >> big;
    Bigger[small].push_back(big);
    Smaller[big].push_back(small);
  }

  for(int i=1; i<=v; i++){
    for(int x : Bigger[i]){
      relation[i][x] = 1;
      relation[x][i] = 1;
    }

    for(int x : Smaller[i])
      DFS(x, 1, i);  
  }

  int ans = 0;
  for(int i=1; i<=v; i++){
    bool flag = true;
    for(int j=1; j<=v; j++){
      if(i!=j && relation[i][j]==0)
        flag = false;
    }
    if(flag)
     ans++;
  }
  cout << ans;
}

前述した方法で規則性をうまく実現し,例示的な検証により自信を得,提出した.

タイムアウトを表示します.
未アクセスの頂点を更新し続ける方式で実現されているため,同じ関係性を再探索することによって生じる問題である可能性がある.
どのようにアプローチすればよいのか考え直したが,各頂点間の関係を更新する方法を時間を超えない方法で構想することは難しい.検索を素早く放棄するのは、やはり新しいアルゴリズムです.

コンセプト

Floyd-Warshallアルゴリズム

// 플로이드-와샬 핵심내용
// 모든 정점을 중간 정점으로 한번씩 잡아서
// 다시 모든 정점을 시작과 끝으로 설정해 중간 정점을 거칠 때 최단경로가 발생하는 지 확인
for(int k = 1; k<= n; k++){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j<=n; j++){
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
        }
    }
}

図の中で頂点間の最短距離を求めるアルゴリズムは多くの種類があり、代表的なのはドエストラ、ベルモンフォードアルゴリズムで、2つのアルゴリズムはいずれも「1つの頂点からすべての頂点までの最短距離」を求めるアルゴリズムである.しかし、現在問題で要求されているのは距離の値自体が重要ではなく、距離で表されるすべての頂点の関係であり、「すべての頂点からすべての頂点までの最短距離」のアルゴリズムfloyd-washallアルゴリズムを採用することができる.
アルゴリズム自体の説明には良い文章があるので、リンクとして残しておきます.
Flood-Whallアルゴリズム
すべての頂点間の距離(関係)というコア要素を理解した.
無知なやり方ですが、それを理解して自分なりに試してみました.
そして、この問題を解決する良いアルゴリズムを知った.
多くの面から言えば、一つの問題から得られたのは多くの問題だ.

正解C++コード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair <ll, ll>;

#define INF 40000

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  //freopen("inp.txt", "r", stdin);
  
  int v, e;
  cin >> v >> e;
  vector<vector<int>> relation(v+1, vector<int>(v+1, INF));
  
  for(int i=1; i<=v; i++)
    relation[i][i] = 0;

  while(e--){
    int small, big;
    cin >> small >> big;
    relation[small][big] = 1;
  }

  for(int mid=1; mid<=v; mid++){
    for(int src=1; src<=v; src++){
      for(int dst=1; dst<=v; dst++)
        relation[src][dst] = min(relation[src][dst], relation[src][mid]+relation[mid][dst]); 
    }
  }

  int ans = 0;
  for(int i=1; i<=v; i++){
    bool flag = true;
    for(int j=1; j<=v; j++){
      if(relation[i][j]==INF && relation[j][i] == INF)
        flag = false;
    }
    if(flag)
     ans++;
  }
  cout << ans;
}