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