@codeforces - 117C@ Cycle

客官°小女子只卖身不卖艺 2023-06-01 13:56 12阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

给定一个竞赛图（有向完全图），请找出里面的某个三元环，或者判断不存在这样的环。

**Input**  
第一行包含一个整数 n (1 ≤ n ≤ 5000)。  
接下来 n 行包含这个图的邻接矩阵，其中 A\[i, j\] = 1 表示存在一条 i 到 j 的边。  
保证 A\[i, i\] = 0, A\[i, j\] ≠ A\[j, i\] (1 ≤ i, j ≤ n, i ≠ j)。

**Output**  
如果无解，输出 -1；否则输出三个不同的顶点 a1, a2, a3 使得 A\[a1, a2\] = 1, A\[a2, a3\] = 1, A\[a3, a1\] = 1。  
任意解即可。

**Examples**  
**Input**  
5  
00100  
10000  
01001  
11101  
11000  
**Output**  
1 3 2

**Input**  
5  
01111  
00000  
01000  
01100  
01110  
**Output**  
\-1

## @solution@ ##

根据竞赛图的性质，如果有环，则一定存在三元环。证明可以通过一个 n 元环一步步缩成一个三元环。

那么假如前 i 个点没有三元环，则一定构成 DAG，考虑维护前 i 个点的拓扑序 p\[1...i\]。  
考虑加入第 i + 1 个点，如果依然无法构成环，则存在一个 j 使得 p\[1...j\] 连向 i + 1 且 i + 1 连向 p\[j+1...i\]。将 i 塞到 j 和 j+1 之间即可。  
否则，可以反证证明出一定存在一个 j 使得 i 连向 p\[j\] 且 p\[j+1\] 连向 i。而这就是我们要找的三元环。

## @accepted code@ ##

#include<cstdio> const int MAXN = 5000; int A[MAXN + 5][MAXN + 5], n; char str[MAXN + 5]; int nxt[MAXN + 5]; int main() { scanf("%d", &n); for(int i=1;i<=n;i++) { scanf("%s", str + 1); for(int j=1;j<=n;j++) A[i][j] = str[j] - '0'; } int hd = 1, tl = 1; nxt[1] = -1; for(int i=2;i<=n;i++) { nxt[i] = -1; if( A[i][hd] ) { int p = nxt[hd]; while( p != -1 ) { if( A[p][i] ) { printf("%d %d %d\n", p, i, hd); return 0; } p = nxt[p]; } nxt[i] = hd, hd = i; } else if( A[tl][i] ) { int p = hd; while( p != tl ) { if( A[i][p] ) { printf("%d %d %d\n", i, p, tl); return 0; } p = nxt[p]; } nxt[tl] = i, tl = i; } else { int p = hd; while( true ) { if( A[p][i] && A[i][nxt[p]] ) break; p = nxt[p]; } int q = hd; while( q != p ) { if( A[i][q] ) { printf("%d %d %d\n", i, q, p); return 0; } q = nxt[q]; } q = nxt[nxt[p]]; while( q != -1 ) { if( A[q][i] ) { printf("%d %d %d\n", q, i, nxt[p]); return 0; } q = nxt[q]; } nxt[i] = nxt[p], nxt[p] = i; } } puts("-1"); }

## @details@ ##

tips：代码写得其实和 solution 描述的有一点点不一样，具体表现是我代码中是不管三七二十一先插入过后才判断是否有这样一个三元环。。。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11381706.html