C - 友達の友達 〜ABC016〜

問題

C - 友達の友達

考え方

制約条件が難しくないので割と簡単です。例えば，以下のようにして解くことができます。

• ある人Aとして，Aが友達Bを見て友達Bをチェックしておく（ set などで）→その友達Bの友達Cを見る→ Cがset に入っていない友達だったら，AにとってCは友達の友達

ただダイクストラ法の勉強にもなるのでそっちで解くのがオススメかなと思います。（今回は上の愚直解で書いてみました。）

Accepted Program

#include <iostream>
#include <set>
using namespace std;

int stand[11];
int dp[11][11];

void init (int n, int num) {
  for (int i = 0; i <= n; i++) {
    stand[i] = 0;  
  } 
  if (num == 0) {  
    for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= n; j++) {
        dp[i][j] = 0;  
      }  
    }
  }
}

int dfs(int n, int x) {
  set<int> ans;
  stand[x] = 1;
  for (int i = 1; i <= n; i++) {
    if (dp[x][i] == 1 && stand[i] == 0) {
      stand[i] = 1;
      for (int j = 1; j <= n; j++) {
        if (dp[i][j] == 1 && stand[j] == 0) {
          ans.insert(j);  
        }  
      }  
      stand[i] = 0;
    } 
  }  
  int answer = ans.size();
  for (auto q = ans.begin(); q!= ans.end(); ++q) {
    if (dp[x][*q] == 1) {
      answer--;  
    }    
  }
  return answer;
}

int main () {
  int n, m;
  cin >> n >> m;
  init (n, 0);
  int s, ss;
  for (int i = 0; i < m; i++) {
    cin >> s >> ss;
    dp[s][ss] = 1;
    dp[ss][s] = 1;  
  }    
  for (int i = 1; i <= n; i++) {
    init(n, i);
    cout << dfs(n, i) << endl;  
  }
}