Triangle LOVE
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1462 Accepted Submission(s): 615

Problem Description
Recently, scientists find that there is love between any of two people. For example, between A and B, if A dont 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,ij). 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 Author BJTU Source 2012 Multi-University Training Contest 3

?Download sourceCode.cpp
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
const double eps=1e-8;
 
#define MEM(a) memset(a,0,sizeof(a));
#define FOR(i,n) for(int i=0;i<n;i++)
 
int outd[10001],start[10001],dfn[10001],low[10001],same[10001];     //startilastshow
int cnt,index;
bool used[5001];
int ans[2010];
int n;
bool ffflag;
bool co[2010][2010];
struct edge
{
    int to,next;
} e[4000100];
 
void insert(int a,int b)
{
    e[cnt].to=b;
    e[cnt].next=start[a];
    start[a]=cnt++;//
}
void ini()
{
    ffflag = false;
    index=0;
    cnt=0;
    memset(start,-1,sizeof(start));
    for(int i =1; i <= n; i ++){
        for(int j = 1;j <= n; j ++)
            co[i][j] = false;
    }
    MEM(dfn);
    MEM(low);
    MEM(outd);
    for(int i = 1; i <= n; i ++)
        ans[i] = 0;
}
 
void tarjan(int i,int father)
{
    dfn[i]=++index;  //dfndfs
    int id=start[i];
    while(id!=-1)    //
    {
        int j=e[id].to;
        if(j==father)
        {
            id=e[id].next;
            continue;
        }
        if(father != -1 && co[j][father]){
            ffflag = true;//ijifather
            //cout << " i"<< i << " j" << j << " f"<< father;
        }
        if(!dfn[j])         //jj
        {
            tarjan(j,i);
        }
        id=e[id].next;
    }
}
 
int main()
{
    int t;
    int i, j;
    int cct = 0;
    scanf("%d", &t);
    while(t--)
    {
        cct ++;
        char d;
        scanf("%d", &n);
        getchar();
        ini();
        for(i =1; i <= n; i ++  ){
            for(j=1; j <= n; j ++)
            {
                d = getchar();
                if(d == '1'){
                insert(i,j);
                co[i][j] = true;
                }
            }
            getchar();
        }
        for(i =1; i <= n; i ++)
        {
            if(dfn[i]==0)
            {
                tarjan(i,-1);  //
            }
        }
        printf("Case #%d: ", cct);
        if(ffflag)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}