Triangle LOVE
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 3479 Accepted Submission(s): 1350
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 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
Recommend
zhoujiaqi2010 | We have carefully selected several similar problems for you:
RE:三角恋 → → 判断是否成环。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 char map[2020][2020]; 7 int indegree[2020]; 8 int n; 9 bool Solve()10 {11 queue q;12 for(int i = 0; i < n; i++)13 {14 if(indegree[i] == 1)15 q.push(i);16 }17 int num = 0;18 while(!q.empty())19 {20 int temp = q.front();21 q.pop();22 num++;23 for(int i = 0; i < n; i++)24 {25 if(map[temp][i])26 {27 indegree[i]--;28 if(indegree[i] == 0) 29 q.push(i);30 }31 } 32 }33 if(num == n)34 return false;35 else36 return true;37 } 38 int main()39 {40 int t, temp = 1;41 scanf("%d", &t);42 while(t--)43 {44 scanf("%d", &n);45 memset(indegree, 0, sizeof(indegree));46 for(int i = 0; i < n; i++)47 {48 scanf("%s", map[i]);49 for(int j = 0; j < n; j++)50 if(map[i][j] == '1')51 indegree[j]++;52 }53 if(Solve())54 printf("Case #%d: Yes\n", temp++);55 else56 printf("Case #%d: No\n", temp++);57 } 58 return 0; 59 }
1 #include2 #include 3 #include 4 using namespace std; 5 char map[2020][2020], indegree[2020]; 6 int n; 7 bool Tsort() 8 { 9 int m;10 for(int i = 0; i < n; i++)11 {12 m = -1;13 for(int j = 0; j < n; j++)14 {15 if(indegree[j] == 0)16 {17 m = j;18 break;19 }20 }21 if(m == -1)22 return true;23 indegree[m]--;24 for(int j = 0; j < n; j++)25 {26 if(map[m][j] == '1')27 indegree[j]--;28 }29 }30 return false;31 }32 int main()33 {34 int t, Q = 1;35 scanf("%d", &t);36 while(t--)37 {38 memset(indegree, 0, sizeof(indegree));39 scanf("%d", &n);40 for(int i = 0; i < n; i++)41 {42 scanf("%s", map[i]);43 for(int j = 0; j < n; j++)44 if(map[i][j] == '1')45 indegree[j]++; 46 } 47 if(Tsort())48 printf("Case #%d: Yes\n", Q++);49 else50 printf("Case #%d: No\n", Q++);51 }52 return 0;53 }