[题解] hdu 4324 Triangle LOVE (拓扑排序)

- 传送门 -

　http://acm.hdu.edu.cn/showproblem.php?pid=4324
　

# Triangle LOVE

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

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). A_i,j = 1 means i-th people loves j-th people, otherwise A_i,j = 0.
It is guaranteed that the given relationship is a tournament, that is, A_i,i= 0, A_i,j ≠ A_j,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

Sample Input

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

Sample Output

Case #1: Yes
Case #2: No

Source

2012 Multi-University Training Contest 3

- 题意 -

　n 个人, 每两个人间一定有 单向 喜欢的关系, 问有没有三角恋.
　((A o B, B o C, C o A))
　

- 思路 -

　拓扑排序模板.
　重点在于分析得到, 只要成环就一定有三角恋.(结合两人间一定有单向喜欢的关系来看)
　假设有((a o b o c... o y o z o a)) 这样一个环, 首先看 (a) 和 (c), 如果 (c) 向 (a) 连边则成环, 所以一定是 (a) 向 (c) 连边, 同理推 (d) (e)...到 (y) 的时候, (a) 向 (y) 连边, 则(a,y,z) 成环, (y) 向 (a) 连边, 则(a,x,y) 成环.
　
　细节见代码.
　

- 代码 -

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

const int N = 2e3 + 5;

int IN[N];
int mat[N][N];
char map[N][N];
int n, cas, ans, x;
vector<int>Q[N];
queue<int>q;

void topo() {
	for(int j=1;j<=n;j++)
    {
      int k;
      for(k=1;k<=n;k++)
      if(IN[k]==0)break;
      if(k==n+1)
      {
        ans = n;
        break;
      }else{
        IN[k]--;
        for(int p=1;p<=n;p++) {
            if(map[k][p-1]=='1' &&IN[p]!=0)
            IN[p]--;
        }
      }
    }
}

int main() {
	scanf("%d", &cas);
	for (int c = 1; c <= cas; ++ c) {
		scanf("%d", &n);	
		memset(IN, 0, sizeof (IN));
		ans = 0;
		for (int i = 1; i <= n; ++i) {
			scanf("%s", map[i]);
			for (int j = 0; j < n; ++j)
				if (map[i][j] == '1')
					IN[j+1] ++;
		}
		topo();
		if (ans == 0) printf("Case #%d: No
", c);
		else printf("Case #%d: Yes
", c);
	}
	return 0;
}