[竞赛图三元环存在性判断] HDU 4324 Triangle LOVE

给一个竞赛图 判断是否有三元环
首先 如果我们任意一个环 就可以找到一个三元环
证明：

假设有环上三个相邻的点a-> b-> c

• 如果c->a有边 就已经形成了一个三元环
• 如果c->a没边 那么a->c肯定有边 这样就形成了一个n-1元环 递归即可

我们可以考虑Tarjan求出强连通分量即可一个强连通分量必定包含一个环
不考虑读入 判断单次 $O(n+m)$ 也就是 $O(n^2)$

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define cl(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair<int,int> abcd;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}
inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(char *s){
  char c=nc(); int len=0;
  for (;!(c>='0' && c<='1');c=nc());
  for (;c>='0' && c<='1';s[++len]=c,c=nc()); s[++len]=0; 
}

const int N=2005;
const int M=N*N;
struct edge{
  int u,v,next;
}G[M];
int head[N],inum;
inline void add(int u,int v){
  int p=++inum; G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p;
}
int pre[N],low[N],clk;
int scc[N],cnt,tot[N];
int Stack[N],pnt;
#define V G[p].v
inline void dfs(int u){
  pre[u]=low[u]=++clk; Stack[++pnt]=u;
  for (int p=head[u];p;p=G[p].next)
    if (!pre[V])
      dfs(V),low[u]=min(low[u],low[V]);
    else if (!scc[V])
      low[u]=min(low[u],pre[V]);
  if (low[u]==pre[u]){
    ++cnt;
    while (Stack[pnt]!=u) scc[Stack[pnt--]]=cnt,tot[cnt]++; scc[Stack[pnt--]]=cnt,tot[cnt]++; 
  }
}

int n;

int main(){
  int T,Case=0; char s[N];
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  read(T);
  while (T--){
    read(n);
    for (int i=1;i<=n;i++){
      read(s);
      for (int j=1;j<=n;j++)
    if (s[j]=='1')
      add(i,j);
    }
    for (int i=1;i<=n;i++)
      if (!pre[i])
    dfs(i);
    int flag=0;
    for (int i=1;i<=cnt;i++)
      flag|=tot[i]>=3;
    printf("Case #%d: %s\n",++Case,flag?"Yes":"No");
    cl(pre); cl(low); clk=0; cl(tot); cnt=0; cl(scc);
    cl(head); inum=0;
  }
  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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

继续考虑 竞赛图不存在任何环 也就是一个DAG 那么他的度数数组一定是0~n-1各出现一次
不考虑读入 直接$O(n)$判断

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define cl(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair<int,int> abcd;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}
inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(char *s){
  char c=nc(); int len=0;
  for (;!(c>='0' && c<='1');c=nc());
  for (;c>='0' && c<='1';s[++len]=c,c=nc()); s[++len]=0; 
}

const int N=2005;

int n;
int deg[N],vst[N];

int main(){
  int T,Case=0; char s[N];
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  read(T);
  while (T--){
    read(n);
    for (int i=1;i<=n;i++){
      read(s);
      for (int j=1;j<=n;j++)
    if (s[j]=='1')
      deg[i]++;
    }
    int flag=0; ++Case;
    for (int i=1;i<=n && !flag;i++)
      if (vst[deg[i]]!=Case)
    vst[deg[i]]=Case;
      else
    flag=1;
    printf("Case #%d: %s\n",Case,flag?"Yes":"No");
    cl(deg);
  }
  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