[HDU 4324] Triangle LOVE （拓扑排序，DFS）

本文主要是介绍[HDU 4324] Triangle LOVE （拓扑排序，DFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HDU - 4324
题意是，一张有 N个点的图，保证每两个点之间有且只有一条有向边连接
求是否存在三元环
用拓扑排序判环，如果存在环，则一定存在三元环
证明如下：
不存在二元环
设存在 n(n>=3)元环 p1->p2->p3->…->pn->p1
1) 若存在边 p3->p1，则存在三元环 (p1->p2->p3->p1)
2) 若不存在 p3->p1，则必然存在 p1->p3
那么 p1->p3->…->pn->p1又构成 n-1元环
递归证明可得，如果存在环，必然存在三元环

但其实这题只要无脑DFS一遍，标记走过的点不再走
在DFS的过程中碰到环的时候判断一下深度差是否为2就好了
因为DFS一定能走出所有点所在的所有环

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define LL long long
#define ULL unsigned long long
#define pow2(a) a*a
int maxx(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
int abss(int a){return a<0?(-a):a;}const int maxn=2e3+10;
int N;
char Map[maxn][maxn];
int ind[maxn];
bool inq[maxn];
int que[maxn*4];int main()
{int T;scanf("%d", &T);for(int ck=1; ck<=T; ck++){CLR(ind);CLR(inq);scanf("%d", &N);for(int i=0; i<N; i++){scanf(" %s", Map[i]);for(int j=0; j<N; j++) if(Map[i][j]=='1') ind[j]++;}int qhead=0,qtail=0;for(int i=0; i<N; i++) if(!ind[i]) {que[++qtail]=i;}while(qhead<qtail){int u=que[++qhead];inq[u]=1;for(int v=0; v<N; v++){if(Map[u][v]=='0') continue;ind[v]--;if(!ind[v]) que[++qtail]=v;}}bool ok=1;for(int i=0; i<N; i++) ok&=inq[i];printf("Case #%d: ", ck);if(!ok) puts("Yes");else puts("No");}return 0;
}