2644 촌수계산

n명이 있고 m개의 간선이 주어졌을 때 s,e의 촌수를 계산한다. n<=100이라 간선은 배열로 만들고 dfs로 1씩 증가시키면 된다.

#include <stdio.h>
#include <queue>
using namespace std;
 
int main() {
    int n, a[101][101] = { 0, }, s, e, m, d[101] = { 0, };
    scanf("%d%d%d%d", &n, &s, &e, &m);
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        a[u][v] = a[v][u] = 1;
    }
    queue<int> q;
    q.push(s);
    d[s] = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        if (x == e) {
            printf("%d", d[x] - 1);
            return 0;
        }
        for (int i = 1; i <= n; i++) {
            if (!a[x][i] || d[i]) continue;
            d[i] = d[x] + 1;
            q.push(i);
        }
    }
    printf("-1");
    return 0;
}