首页 > 搜索 > DFS搜索 > HDU 4324-Triangle LOVE-DFS-[解题报告]HOJ
2015
05-23

HDU 4324-Triangle LOVE-DFS-[解题报告]HOJ

Triangle LOVE

问题描述 :

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”.

输入:

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).

输出:

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).

样例输入:

2
5
00100
10000
01001
11101
11000
5
01111
00000
01000
01100
01110

样例输出:

Case #1: Yes
Case #2: No

/**
[有向环] hdu 4324 Triangle LOVE
判断一个有向图中是否有环,因为任意两点都有一条边,故该图只有一个子图
现在想来dfs,拓扑排序什么的都弱爆了,所有结点的入度都>0就AC
*/
#include <stdio.h>
#include <string.h>
int in[2001];
int main(){
	int t,cas = 0,i,j,n;
	scanf("%d",&t);
	while(t--){
		memset(in,0,sizeof(in));
		scanf("%d\n",&n);
		for(i = 0;i < n; ++i){
			for(j = 0; j < n; ++j)
				if(getchar() == '1')
					in[j]++;
			getchar();
		}
			
		for(i = 0; i < n; ++i)
			in[n] += (in[i] != 0);
		printf(in[n] == n ? "Case #%d: Yes\n" : "Case #%d: No\n",++cas);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/cscj2010/article/details/7888670