竞赛图判断是否存在三元环-CF-117C_强连通的竞赛图必有长度为3的圈

题目：传送门

 给你一张竞赛图，问是否存在三元环，若有，则按顺序输出；反之，输出-1。

竞赛图
把一张有n个节点无向完全图，每条边加一个方向，这就是竞赛图。

思路：

推荐一个讲解视频：NOIP系列模拟题讲解2

有一个定理：如果一个竞赛图存在大于等于三元环，则一定存在3元环。

有了这个定理就随便写咯。直接dfs，用pre数组记录祖先。找到了就输出。

vis[i]=0表示这个点还没被访问过
vis[i]=-1表示这个点被访问过，但是子孙还没被访问完
vis[i]=1表示这个点被访问过，且子孙被访问完了

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 5000+5;
int n,ans,tok;
vector<int>mp[N];
char ar[N];
int vis[N],tsum[N],pre[N];
inline void init(){
    for(int i=0;i<=n;++i){
        mp[i].clear();
    }
    tok=n+1;
    memset(vis,0,sizeof(vis));
}
bool dfs(int u,int fa,int ye){
    vis[u]=-1;
    int len=mp[u].size();
    for(int i=0;i<len;++i){
        int v=mp[u][i];
        if(vis[v]==1)continue;
        pre[v]=u;
        if(vis[v]==-1){
            ans=v;
            return true;
        }else {
            if(dfs(v,u,fa))return true;
        }
    }
    vis[u]=1;
    tsum[--tok]=u;
    return false;
}
bool tuopu(){
    for(int i=1;i<=n;++i){
        if(vis[i])continue;
        if(dfs(i,-1,-1))return true;
    }
    return false;
}
int main(){
    while(~scanf("%d",&n)){
        init();
        for(int i=1;i<=n;++i){
            scanf("%s",ar+1);
            for(int j=1;j<=n;++j){
                if(ar[j]=='1'){
                    mp[i].push_back(j);
                }
            }
        }
        if(tuopu()){
            printf("%d %d %d\n",pre[pre[ans]],pre[ans],ans );
        }else printf("-1\n");
    }
    return 0;
}
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