# Triangle LOVE

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1387    Accepted Submission(s): 584

Problem Description
Recently, scientists find that there is love between any of two people. For example, between A and B, if A don’t love B, then B must love A, vice versa. And there is no possibility that two people love each other, what a crazy world!
Now, scientists want to know whether or not there is a “Triangle Love” among N people. “Triangle Love” means that among any three people (A,B and C) , A loves B, B loves C and C loves A.
Your problem is writing a program to read the relationship among N people firstly, and return whether or not there is a “Triangle Love”.

Input
The first line contains a single integer t (1 <= t <= 15), the number of test cases.
For each case, the first line contains one integer N (0 < N <= 2000).
In the next N lines contain the adjacency matrix A of the relationship (without spaces). Ai,j = 1 means i-th people loves j-th people, otherwise Ai,j = 0.
It is guaranteed that the given relationship is a tournament, that is, Ai,i= 0, Ai,j ≠ Aj,i(1<=i, j<=n,i≠j).

Output
For each case, output the case number as shown and then print “Yes”, if there is a “Triangle Love” among these N people, otherwise print “No”.
Take the sample output for more details.

Sample Input
2
5
00100
10000
01001
11101
11000

5
01111
00000
01000
01100
01110

Sample Output
Case #1: Yes
Case #2: No

/**

*/
#include <stdio.h>
#include <string.h>
int t,n;
//存储的是节点的入度
int in_degree[2010];
//存储的是i,j两个节点的关系，1:i love j,0:j love i

int main()
{
bool flag;//true表示为有三角恋，false表示为没有三角恋
scanf("%d",&t);
for(int i = 1; i <= t;i++)
{

scanf("%d",&n);
flag = false;
//将所有的节点入度初始化为0
memset(in_degree,0,sizeof(in_degree));
for(int j = 0; j < n; j++)
{
for(int k=0;k<n;k++)
in_degree[k]++;
}

for(int j=0;j<n;j++)
{
int k;
for(k=0;k<n;k++)
if(in_degree[k]==0)break;//找出入度为0的节点
if(k==n)//任何一个节点的入度都不为0，说明存在环了，则必有三角恋
{
flag = true;
break;
}else{
//将这个点的入度设为-1，避免再次循环时有查到了这个节点，
//此时说明这个点已经从集合中除掉了
in_degree[k]--;
for(int p=0;p<n;p++)
{
//把从这个节点出发的引起的节点的入度都减去1
in_degree[p]--;
}
}
}
if(flag)
printf("Case #%d: Yes\n",i);
else printf("Case #%d: No\n",i);
}
return 0;
}

+ 订阅