题意：给出一堆人的喜爱关系，判断有没有三角恋-_-||
其实就是判断是否存在三条边的环。
一开始我是这么想的：
先拓扑排序，如果没有环那就直接No
如果有环？挑出环里的任意一个点（拓扑排序结束后不在拓扑序里面的点就在环里），然后从这个点开始dfs，看三步之后能不能回到这个点。（可以证明，只要考察一个点就行）
然而TLE了= =
其实仔细想想可以发现，后面那个dfs没有必要。
注意一个细节：A[i][j]<>A[j][i]。也就是说若i到j不通，那么j到i一定通
可以证明，若这样的图中存在环，那么一定存在三角环（证明Reference：http://blog.****.net/xiaofengcanyuexj/article/details/29179639）
数据不大，邻接矩阵就ok
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define MAXN 2100 int a[MAXN][MAXN];
int d[MAXN];
bool ok;
int N,T,x,y; void topsort()
{
bool circle=false;
int i=;
while(i<N)
{
int j=;
while(d[j]!=) j++;
if(j==N+)
{
circle=true;
break;
}
d[j]=-;
for(int k=;k<=N;k++)
if(a[j][k]==)
{
d[k]--;
a[j][k]=;
}
i++;
}
if((circle)&&(N>=))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
} int main()
{
cin>>T;
for(int Times=;Times<=T;Times++)
{
cin>>N;
memset(d,,sizeof(d));
memset(a,,sizeof(a));
char ch[];
for(int i=; i<=N; i++)
{
scanf("%s",ch);
for(int j=;j<=N;j++)
{
if (ch[j-]=='')
{
d[j]++;
a[i][j]=;
}
}
}
cout<<"Case #"<<Times<<": ";
topsort(); }
return ;
}
顺便记两个拓扑排序模板：
邻接矩阵：见本题
邻接表：
邻接表建图：
void addedge(int x,int y) //x->y
{
d[y]++; //d[i]:点i的入度
ev[cnt]=y; //ev[i]:第i条边的destination
nxt[cnt]=head[x]; //nxt[i]:第i条边的下一条边
head[x]=cnt; //head[i]:由i节点出发的第一条边的序号
cnt++;
} -------------------------------------------------------------------------------- void topsort()
{
vector<int> vec;
for(int i=; i<=N; i++)
if(d[i]==) vec.push_back(i);
for(int i=; i<vec.size(); i++)
{
int x=vec[i];
for(int j=head[x]; j!=; j=nxt[j])
{
int y=ev[j];
d[y]--;
if(d[y]==) vec.push_back(y);
}
}
int last=vec.size();
//last!=N说明有环
}
如果嫌慢可以把vector改写成普通数组
//PS：Reference的那个博主是地大的本科生，本科毕业就拿到了人人+去哪儿offer，orz