qbxt的题：找一个三元环

有向图中找一个三元环

题意：

考虑 N 个人玩一个游戏，任意两个人之间进行一场游戏（共 N*(N-1)/2 场），且每场一定能分出胜负。现在，你需要在其中找到三个人构成的这样的局面：A战胜B，B战胜C，C战胜A。

分析：

注意到一个重要的条件，就是图中有n*(n-1)/2条有向边。

正解的做法：在图中找一个环，如果存在一个环，那么一定存在一个三元环。

为什么？

对于一个环，是这样的，枚举除起点外的前两个点，即123，如果3可以到1，那么说明存在一个三元环。

否则，说明1一定连向了3，然后判断第4是否连向1即可。依次类推。

一直判断下去，到8号点，可行的就行了。

否则，剩下的三个点一定可以了。

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cctype>
 6 #include<cmath>
 7 #include<set>
 8 #include<queue>
 9 #include<vector>
10 #include<map>
11 using namespace std;
12 typedef long long LL;
13 
14 inline int read() {
15     int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f=-1;
16     for (; isdigit(ch); ch=getchar()) x = x * 10 + ch - '0'; return x * f;
17 }
18 
19 const int N = 5005; 
20 
21 char s[N][N];
22 int top, n, vis[N], sk[N], pos[N];
23 vector<int> ans;
24 
25 
26 void pr() {
27     for (int i = 1; i < ans.size() - 1; ++i) {
28         if (s[ans[i + 1]][ans[0]] == '1') {
29             cout << ans[0] << " " << ans[i] << " " << ans[i + 1];
30             exit(0);
31         }
32     }
33 }
34 
35 void dfs(int u) {
36     vis[u] = 1, sk[++top] = u; pos[u] = top;
37     for (int i = 1; i <= n; ++i) {
38         if (s[u][i] != '1') continue;
39         if (vis[i] == 1) {
40             int len = top - pos[i] + 1;
41             for (int j = pos[i]; j <= top; ++j) ans.push_back(sk[j]);
42             pr();
43         } else if (vis[i] == 0) {
44             dfs(i);
45         }
46     }
47     --top; vis[u] = 2;
48 }
49 
50 int main() {
51     
52     freopen("game.in","r",stdin);
53     freopen("game.out","w",stdout);
54     
55     n = read();
56     for (int i = 1; i <= n; ++i) scanf("%s",s[i] + 1);
57     for (int i = 1; i <= n; ++i) {
58         if (!vis[i]) dfs(i);
59     }
60     puts("-1");
61     return 0;
62 }
63 /*
64 5 
65 00100 
66 10000 
67 01001 
68 11101 
69 11000 
70 
71 */