Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=3497
In our increasingly interconnected world, it has been speculated that everyone on Earth is related to everyone else by no more than six degrees of separation. In this problem, you must write a program to find the maximum degree of separation for a network of people. For any two people, the degree of separation is the minimum number of relationships that must be traversed to connect the two people. For a network, the maximum degree of separation is the largest degree of separation between any two people in the network. If there is a pair of people in the network who are not connected by a chain of relationships, the network is disconnected. As shown below, a network can be described as a set of symmetric relationships each of which connects two people. A line represents a relationship between two people. Network A illustrates a network with 2 as the maximum degree of separation. Network B is disconnected. Network A: Max. degree of separation = 2 Network B: Disconnected Input The input consists of data sets that describe networks of people. For each data set, the first line has two integers: P (2 ≤ P ≤ 50), the number of people in the network, and R (R ≥ 1), the number of network relationships. Following that first line are R relationships. Each relationship consists of two strings that are names of people in the network who are related. Names are unique and contain no blank spaces. Because a person may be related to more than one other person, a name may appear multiple times in a data set. The final test case is followed by a line containing two zeroes. Output For each network, display the network number followed by the maximum degree of separation. If the network is disconnected, display ‘DISCONNECTED’. Display a blank line after the output for each network. Use the format illustrated in the sample output.
Sample Input 4 4 Ashok Kiyoshi Ursala Chun Ursala Kiyoshi Kiyoshi Chun 4 2 Ashok Chun Ursala Kiyoshi 6 5 Bubba Cooter Ashok Kiyoshi Ursala Chun Ursala Kiyoshi Kiyoshi Chun 0 0
Sample Output Network 1: 2 Network 2: DISCONNECTED Network 3: DISCONNECTED
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
// 2 solutions: floyd warshall or double dfs
int main()
{
int n,e,tc=1;
string a,b;
while(scanf("%d %d",&n,&e),(n+e)!=0){
unordered_map < string,int> idxMap;
vector<vector<int>> dist(n,vector<int>(n,1e6));
int idx=0;
for(int i=0;i < e;i++){
cin >> a >> b;
if(!idxMap.count(a)) idxMap[a] = idx++;
if(!idxMap.count(b)) idxMap[b] = idx++;
dist[idxMap[a]][idxMap[b]] = 1;
dist[idxMap[b]][idxMap[a]] = 1;
}
for(int k=0;k<n;k++)
for(int i=0;i < n;i++)
for(int j=0;j < n;j++)
dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
int diameter = 0;
bool disconnected = false;
for(int i=0;i < n&&!disconnected;i++){
for(int j=0;j < n&&!disconnected;j++){
if(i!=j){
diameter = max(dist[i][j],diameter);
if(dist[i][j] == 1e6) disconnected = true;
}
}
}
printf("Network %d: ",tc++);
if(disconnected) printf("DISCONNECTED\n\n");
else printf("%d\n\n",diameter>;
}
}
Input
Ashok Kiyoshi Ursala Chun Ursala Kiyoshi
Kiyoshi Chun
4 2
Ashok Chun Ursala Kiyoshi
6 5
Bubba Cooter Ashok Kiyoshi Ursala Chun
Ursala Kiyoshi Kiyoshi Chun
0 0
Output
Network 2: DISCONNECTED
Network 3: DISCONNECTED
Demonstration
UVA Online Judge solution - 1056-Degrees of Separation - UVA Online Judge solution in C,C++,java