2 5 00100 10000 01001 11101 11000 5 01111 00000 01000 01100 01110
Case #1: Yes Case #2: No
题意：给出你所有人的关系，然后让你判断一下是否存在三角恋或多角恋。
分析：我们可以根据关系建一个有向图，假如A喜欢B那么就让A指向B，假如存在三角恋或多角恋那么肯定会形成一个环，我选择用拓扑排序，如果形成环的话肯定不会把所有的数都排序。
注意：用链式前向星的话，边的数组要开到2000*1999之上，，RE了好几次。
心得: 比赛的时候没有想到拓扑，只是想到了并查集，左后还是没有做出来。
并查集可以判断一棵树是不是成环，拓扑才可以判断一个图是不是成环。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 2005
struct node{
int to, next;
}s[20000005];
int in[M], head[M], n, tot, queue[M];
char map[M][M];
void getmap(int a, int b){
s[tot].to = b;
in[b]++;
s[tot].next = head[a];
head[a] = tot++;
}
int toposort(){
bool vis[M];
memset(vis, false, sizeof(vis));
int i, j, iq = 0;
for(i = 0; i < n; i ++){
if(!in[i]){
queue[iq++] = i;
vis[i] = 1;
}
}
for(i = 0; i < iq; i++){
int temp = head[queue[i]];
for(j = temp; j != -1; j = s[j].next){
if(!(--in[s[j].to])){
queue[iq++] = s[j].to;
}
}
}
if(iq < n) return 1;
else return 0;
}
int main(){
int t, v = 1;
scanf("%d", &t);
while(t --){
memset(in, 0, sizeof(in));
memset(head, -1, sizeof(head));
tot = 0;
scanf("%d", &n);
int i, j, flag;
for(i = 0; i < n; i ++){
scanf("%s", map[i]);
for(j = 0; j < n; j ++){
if(map[i][j] == '1'){
getmap(i, j);
}
}
}
printf("Case #%d: ", v++);
flag = toposort();
if(flag) printf("Yes\n");
else printf("No\n");
}
return 0;
}原文：http://blog.csdn.net/shengweisong/article/details/40039621