ABC 016 C - 友達の友達

問題

問題概要

省略

解法

dfsで友達の友達を求めることにした。この時に、dfsの引き数として、現在の頂点と、前回の頂点、探索回数、スタート時点の頂点を持つことにした。前回の頂点は元の頂点に戻るのを禁止しするため。スタート時点を保持しておくのは、例えば、3つの頂点がループになっているときに、頂点1から始めた時に、2回の探索で、頂点3が友達の友達でないかと求まるが、実際は、1と3は友達なので、友達の友達にはならない。そこで、f[u][v]でuとvが友達であるかの情報を入れておいて、2回の探索後に友達でないことを確認すればいい。また、友達の友達を重複してカウントしないように、一度頂点番号をsetに入れている。
グラフの隣接リストと隣接行列を2つ作っている。

ミス

友達を重複してカウントしてしまい、WA。 解説読んだら、ワーシャルフロイドで頂点からの距離が2の位置を求めるだけかとわかり、なるほど。

コード

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int n, m;
vector<int> G[12];
int f[12][12];
int ans = 0;
set<int> tomo;//友達の友達を重複なく入れる

void dfs(int v, int p, int num, int s){
    if(num == 2){
        if(f[v][s] == false) tomo.insert(v);
        return;
    }

    for(auto u : G[v]){
        if(u != p && u != s){
            dfs(u, v, num + 1, s);
        }
    }
}

int main(void){
    cin >> n >> m;
    rep(i, 12)rep(j, 12) f[i][j] = false;
    rep(i, m){
        int a, b; cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
        f[a][b] = f[b][a] = true;
    }

    rep(i, n){
        tomo.clear();
        dfs(i, -1, 0, i);
        printf("%d\n", tomo.size());
    }
    return 0;
}

ワーシャルフロイド法で解いた解法

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int n, m;
int d[12][12];//辺のコスト
void warshall_floyd(){
    for (int k = 0; k < n; ++k){
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < n; ++j){
                d[i][j] = min(d[i][j], d[i][k] + d[j][k]);
            }
        }
    }
}

int main(void){
    cin >> n >> m;
    rep(i, 12)rep(j, 12) d[i][j] = INF;
    rep(i, 12)d[i][i] = 0;
    rep(i, m){
        int a, b; cin >> a >> b;
        a--; b--;
        d[a][b] = d[b][a] = 1;//辺のコストは1
    }

    warshall_floyd();
    
    rep(i, n){
        int ans = 0;
        rep(j, n){
            if(d[i][j] == 2) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}