DWITE Round 2 #4

[A.J]

I noticed that a lot of people implemented Floyd-Warshall for this question.

However, according to me at least, there exists a nicer solution:

c++:

#include<iostream> using namespace std; int n, x, y, ans, num[51], conn[51][51]; main() {         freopen("DATA4.txt","r",stdin);         freopen("OUT4.txt","w",stdout);     for (int t = 0; t < 5; t++)     {         cin >> n;         memset(num, 9999, sizeof(num));         memset(conn, 0, sizeof(conn));         num[1] = ans = 0;         for (int i = 0; i < n; i++)         {             cin >> x >> y;             conn[x][y] = conn[y][x] = 1;             num[y] <?= num[x] + 1;         }         for (int i = 1; i < 50; i++)             for (int j = i + 1; j < 51; j++)                 if (conn[i][j] && (num[i] == num[j]) && num[i] != 9999)                     ans++;         cout << ans << endl;     } }

The basic idea is that if 2 points A and B are connected, and if dist[B] < dist[A] + 1, store dist[A] + 1 in dist[B] (where dist[x] contains distance from 1, and dist[1] = 0, and dist[x] = 999999 for all other values of x). O(n^2) as opposed to Floyd-Warshall's O(n^3).

This solution was taken from the team 'Zaiphyr' from Waterloo Collegiate Institute, and all credit goes to Yusong Men (founder of the aforementioned team).

[yusong]

Nice, Thank You AJ!