Competitive Programming Solutions

292B - Network Topology

27 Dec 2020 — Tags: graphs,implementation — URL

Given a connected graph, $G$, with $n$ nodes, you can determine it’s type by its distribution of node-degrees.

  • bus: $n-2$ nodes with degree $2$, and $2$ nodes with degree $1$ (the extremes).
  • ring: $n$ nodes of degree $2$.
  • star: $n - 1$ nodes with degree $1$ and $1$ node with degree $n-1$.

Time complexity: $O(n \log{n})$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
string solve(vi d)
{
    auto dgone = [](int dg) { return dg == 1; };
    auto dgtwo = [](int dg) { return dg == 2; };
    int n = (int)(d).size();
    sort(begin(d), end(d));
    if (all_of(begin(d), end(d), dgtwo))
        return "ring topology";
    if (all_of(begin(d) + 2, end(d), dgtwo) and
        all_of(begin(d), begin(d) + 2, dgone))
        return "bus topology";
    if (d.back() == n - 1 and all_of(begin(d), end(d) - 1, dgone))
        return "star topology";
    return "unknown topology";
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vi d(n, 0);
    while (m--)
    {
        int u, v;
        cin >> u >> v, u--, v--;
        d[u]++, d[v]++;
    }
    cout << solve(d) << endl;
    return 0;
}

Related posts