Triangle LOVE
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3566 Accepted Submission(s):
1395
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”.
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).
<= 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.
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
题意：给出一个矩阵s[][]如果其中s[i][j]等于1代表i喜欢j，（但是题目保证不可能有两个人互相相爱）现在问这些人的关系中是否存在三角 恋（A爱B，B爱C，C爱A）如果有则输出yes否则输出no
题解：因为题目已经保证不会有两个人互相相爱，所以说成环最少也是三人环，直接拓扑排序判断是否成环即可（要用邻接表做，矩阵会超 时）
#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
#define MAX 2010
using namespace std;
int n,k;
vector<int>map[MAX];
char s[MAX];
int vis[MAX];
void getmap()
{
int i,j;
for(i=1;i<=n;i++)
map[i].clear();
for(i=1;i<=n;i++)
{
scanf("%s",s);
for(j=0;j<n;j++)
{
if(s[j]=='1')
{
map[i].push_back(j+1);
vis[j+1]++;
}
}
}
} void tuopu()
{
int i,j;
queue<int>q;
while(!q.empty())
q.pop();
for(i=1;i<=n;i++)
if(vis[i]==0)
q.push(i);
int u,v;
int ans=0;
while(!q.empty())
{
u=q.front();
ans++;
q.pop();
for(i=0;i<map[u].size();i++)
{
v=map[u][i];
vis[v]--;
if(vis[v]==0)
q.push(v);
}
}
printf("Case #%d: ",k++);
if(ans!=n)
printf("Yes\n");
else
printf("No\n");
}
int main()
{
int t,i,j;
k=1;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(vis,0,sizeof(vis));
getmap();
tuopu();
}
return 0;
}