CF117C Cycle 题解

题目链接：CF117C Cycle

题意：

一个 $\texttt{tournament}$ 是一个没有自环的有向图，同时，每两个点之间有一条边连接。这就是说，对于两个点 $u,v (u\neq v)$，有一条从 $u$ 到 $v$ 的边或一条从 $v$ 到 $u$ 的边。

给你一个 $\texttt{tournament}$，请找出一个长度为 $3$ 的环。

输入格式：

第一行一个正整数 $n(n \le 5\times 10^3)$。

接下来 $n$ 行：一个 $n \times n$ 的邻接矩阵 $a$，由 0 和 1 组成。

若 $a_{i,j}=1$，表示有一条路从 $i$ 通往 $j$。

数据保证 $a_{i,i}=0$ 并且 $a_{i,j} \neq a_{j,i}$。

输出格式

仅一行：任意一种解决方案；若没有，输出 -1。

容易发现这个图就是有向完全图，也就是竞赛图。

根据竞赛题的性质可知，竞赛题如果存在环则一定存在三元环。

于是这道题就是一个简单的判环题，不过我们可以考虑用一种常数更小的判环方法来增加难度

考虑对于一个点 $x$ ，我们能找到两个点 $y,z$ 满足以下形式：

可以证明边 $(x,z)$ 是没有用的，即如果存在包含 $(x,z)$ 的三元环，那么一定存在一个不包含 $(x,z)$ 的三元环。

考虑枚举一个点 $a$ ，其与 $x,z$ 构成了一个三元环，如下图所示。

可以发现无论 $y,a$ 连边的方向如何，均可产生一个不包含边 $(x,z)$ 的三元环。

则根据归纳法，对于每个节点 $x$，我们只需要记录它的一个 $\mathrm{to}(x)$ 。

接着我们枚举 $x,y$ 并检查 $x,\mathrm{to}(x),y$ 是否构成一个三元环即可。

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e3 + 15))

int n,to[N]; char g[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> (g[i] + 1);
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
        if(g[i][j] == '1' && (!to[i] || g[j][to[i]] == '1')) to[i] = j;
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
        if(g[to[i]][j] == '1' && g[j][i] == '1')
            return cout << i << ' ' << to[i] << ' ' << j << '\n', 0;
    }
    cout << "-1" << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/stoorz/solution-cf117c