CF117C Cycle - 洛谷

题目大意

给定一个有向图，无大小为二的环，找出一个大小为

3

的环。

解题思路

tarjan

赛时一开始发现这很 tarjan，复杂度也是

O(n+m)

的，非常地符合。

但后来发现 tarjan 好像会直接判成一个强连通分量，这时候就很难去找一个大小为

3

小环了。

弱化版 tarjan

既然大环都找得出，那么小环怎么会找不出呢，显然是复杂了。

仔细回想一下，tarjan 的复杂度为什么是

O(n+m)

，我认为主要是有标记就可以不用再搜了，那是否能运用一下这个东西呢，答案是可以的。

对于每一个节点只需要存一下父亲节点，遍历一下儿子节点，用儿子节点跟父亲节点判一下，

除此之外如果儿子没搜过，那就搜一下。

于是，一个弱化版 tarjan 就诞生了。

~~（PS：我这样过了之后还以为是 tarjan 启蒙题，最多绿题，万万没想到居然是道蓝题。）~~

AC 代码

CPP

#include<iostream>
#include<cstdio>
using namespace std;
const int N=5005;
int n,k,pre[N],u1,u2,u3;
bool b[N][N],vis[N],flag;
//vis 数组就相当于原版 tarjan 的 dfn 数组了
//flag 存是否已经找到答案
struct edge{
    int v,next;
}e[N*N];
void add(int u,int v){
    e[++k]={v,pre[u]};
    pre[u]=k;
}
void dfs(int u,int fa){
    vis[u]=true;
    if(flag)return;
    //已经找到答案了，不用再搜了，直接结束
    for(int i=pre[u];i;i=e[i].next){
        if(b[e[i].v][fa]){
            flag=true;
            u1=u;
            u2=e[i].v;
            u3=fa;
            return;
        }
        if(!vis[e[i].v])dfs(e[i].v,u);
        //如果没搜过，就搜一下
    }
}
//弱化版 tarjan
int main(){
    scanf("%d\n",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)if(b[i][j]=(getchar()-'0'))add(i,j);
        getchar();
    }
    //建图
    for(int i=1;i<=n;i++)if(!vis[i]){
        dfs(i,0);
        //如果没搜过，就搜一下
        if(flag){
            printf("%d %d %d",u1,u2,u3);
            return 0;
        }
        //找到答案了，直接输出结束
    }
    puts("-1");
    //遍历完了也没找到，输出 -1
    return 0;
}

题解：CF117C Cycle

文章操作