Jin Yong’s Wukong Ranking List(Floyd判环)

发表于 | 阅读次数：

图论不会套模板…………

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
const int maxn = 550;
int mp[maxn][maxn], n;
map<string, int> q;
void floyd()
{
   for(int k=1 ;k<=n;++k)
   {
      for(int i=1 ;i<=n ;++i)
      {
         for(int j=1 ;j<=n ;++j)
         {
            if (mp[i][k] && mp[k][j])
               mp[i][j] = 1;
         }
      }
   }
}string str[22][2];
int main()
{
   int m;
   while (cin >> m)
   {
      q.clear();
      n = 0;
      for (int i = 1; i <= m; ++i)
      {

        cin >> str[i][0]>>str[i][1];

         if (q[str[i][0]] == 0)
            q[str[i][0]] = ++n;
         if (q[str[i][1]] == 0)
            q[str[i][1]] = ++n;
      }

      int ok = 0;
      for (int i = 1; i <= m; ++i)
      {
         floyd();
         if (mp[q[str[i][1]]][q[str[i][0]]] == 1)
         {
            cout << str[i][0] << ' ' << str[i][1] << endl;
            ok = 1;
            break;
         }
         mp[q[str[i][0]]][q[str[i][1]]]=1;
      }
      if(ok==0)
         cout<<0<<endl;
   }
   return 0;
}
0%