The Social Network
Time Limit: 3000/2000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Problem Description
The social network system (SNS) helps people to keep connecting with their friends. Every user in SNS has a friends list. The user can read news posted by the users in his friends list. Friend relation is symmetric - if A is a friend of B, B is always a friend of A.
Another important function in SNS is friend recommendation. One effective way to recommend friends is recommend by mutual friends. A mutual friend between two users A and B, is a user who is a friend of both A and B. A user can not be a friend of himself. For a specific user A, the system will recommend the user who is not himself or his friend, and has mutual friends with A. If more than one such user exists, recommend the one has most mutual friends with A. If still a tie exists, output all of them.
Input
The first line is a integer T (T≤100), the number of test case.
The beginning of each test case is two integers N and Q, the number of friend relationship and the number of query. 1 ≤ N, Q ≤ 1000
The following N lines each contain two different names separated by a single space. Each name consisted by only lowercase letters, and its length is less than or equal to 15. This means the two users are friends. No friend relationship will be given more than once.
The following Q lines each describe a query. Each line contain one user name. The data guarantee that this name appears at least once in above N lines.
Output
For each case, you should output one line containing “Case k: ” first, where k indicates the case number and counts from one. Then for each query, output one line, contains one or more names of recommended friends, separate by a single space, sorted by alphabetical order. If no persons can be recommended, output one line contains “-”.
Sample Input
1
10 11
hongshu digua
yingying hongshu
xmm hongshu
huaxianzi xmm
tangjiejie huaxianzi
xhmz yingying
digua xhmz
zt tangjiejie
xmm lcy
notonlysuccess ljq
hongshu
digua
yingying
xmm
huaxianzi
tangjiejie
xhmz
zt
lcy
notonlysuccess
ljq
Sample Output
Case 1:
xhmz
yingying
digua
digua tangjiejie yingying
hongshu lcy zt
xmm
hongshu
huaxianzi
hongshu huaxianzi
-
-
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 #define N 2002
6 #define NAMELEN 17
7
8 /* id 1..nId */
9 /* id <=> name */
10 #define TC 26
11 #define TM 100000
12 struct __Trie
13 {
14 struct __Trie * ch[ TC ];
15 int id;
16 };
17 typedef struct __Trie Trie;
18 Trie trieMem[ TM ];
19 char nameMem[ N ][ NAMELEN ];
20 int nId, totMem;
21 Trie *root;
22
23 int getIdFromName( char *name ) {
24 char *p = name;
25 Trie **pp = &root;
26 for ( ; ; ) {
27 if ( NULL == (*pp) ) {
28 *pp = trieMem + totMem++;
29 memset( (*pp), 0, sizeof(Trie) );
30 }
31 if ( *p ) {
32 pp = &( (*pp)->ch[ (*p) - 'a' ] );
33 ++p;
34 }
35 else {
36 if ( (*pp)->id ) {
37 return ((*pp)->id);
38 }
39 else {
40 (*pp)->id = ++nId;
41 strcpy( nameMem[ nId ], name );
42 return nId;
43 }
44 }
45 }
46 return 0;
47 }
48 #define getNameFromId(id) nameMem[ (id) ]
49
50 char isFri[ N ][ N ];
51 int friend[ N ][ N ], numFri[ N ];/* friend[ i ][ 1..numFri[i] ] */
52 int mut[ N ][ N ];
53
54 void init() {
55 root = NULL;
56 nId = 0;
57 totMem = 0;
58 memset( isFri, 0, sizeof(isFri) );
59 memset( numFri, 0, sizeof(numFri) );
60 memset( mut, 0, sizeof(mut) );
61 }
62
63 int cmpNameById( const void *a, const void *b ) {
64 return strcmp( getNameFromId(*((int*)a)), getNameFromId(*((int*)b)) );
65 }
66
67
68 void process() {
69 int i, j, k, x, y;
70 for ( k = nId; k > 0; --k ) {
71 for ( i = numFri[ k ]; i > 0; --i ) {
72 x = friend[ k ][ i ];
73 for ( j = i - 1; j > 0; --j ) {
74 y = friend[ k ][ j ];
75 if ( 0 == isFri[ x ][ y ] ) {
76 ++mut[ x ][ y ];
77 ++mut[ y ][ x ];
78 }
79 }
80 }
81 }
82 }
83
84 void query( char *name ) {
85 static int mf[ N ];
86 int i, j, maxMut = 0, k = 0;
87 i = getIdFromName( name );
88 for ( j = nId; j > 0; --j ) {
89 if ( mut[ i ][ j ] > maxMut ) {
90 maxMut = mut[ i ][ j ];
91 k = 1;
92 mf[ 0 ] = j;
93 }
94 else if ( mut[ i ][ j ] == maxMut ) {
95 mf[ k++ ] = j;
96 }
97 }
98 if ( maxMut == 0 ) {
99 puts( "-" );
100 return;
101 }
102 qsort( mf, k, sizeof(mf[0]), cmpNameById );
103 printf( "%s", getNameFromId(mf[0]) );
104 for ( i = 1; i < k; ++i ) {
105 printf( " %s", getNameFromId(mf[i]) );
106 }
107 puts( "" );
108 }
109
110 int main() {
111 int m, q, tc, cc, idA, idB;
112 char nameA[ NAMELEN ], nameB[ NAMELEN ];
113 scanf( "%d", &tc );
114 for ( cc = 1; cc <= tc; ++cc ) {
115 init();
116 scanf( "%d%d", &m, &q );
117 while ( m-- > 0 ) {
118 scanf( "%s%s", nameA, nameB );
119 idA = getIdFromName( nameA );
120 idB = getIdFromName( nameB );
121 if ( (0 == isFri[ idA ][ idB ]) && (idA != idB) ) {
122 isFri[ idA ][ idB ] = isFri[ idB ][ idA ] = 1;
123 friend[ idA ][ ++numFri[idA] ] = idB;
124 friend[ idB ][ ++numFri[idB] ] = idA;
125 }
126 }
127 process();
128 printf( "Case %d:\n", cc );
129 while ( q-- > 0 ) {
130 scanf( "%s", nameA );
131 query( nameA );
132 }
133 }
134 return 0;
135 }
136