题意：判三角恋(三元环)。如果A喜欢B，那么B一定不喜欢A，任意两人一定有关系连接
分析：正解应该是拓扑排序判环，如果有环，一定是三元环，证明。 DFS：从任意一点开始搜索，搜索过的点标记，否则超时。看是否存在两点路程只差等于2，如果存在，则说明有上述的三角环。其他做法。
收获：DFS搜索一定要用vis数组啊，否则很容易超时的
代码(拓扑排序)：
/************************************************
* Author :Running_Time
* Created Time :2015-8-25 19:24:24
* File Name :E_topo.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 2e3 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
char s[N][N];
vector<int> G[N];
int in[N];
int n; bool Topo_Sort(void) {
memset (in, 0, sizeof (in));
for (int i=1; i<=n; ++i) {
for (int j=0; j<G[i].size (); ++j) in[G[i][j]]++;
}
queue<int> Q; int cnt = 0;
for (int i=1; i<=n; ++i) if (!in[i]) Q.push (i);
while (!Q.empty ()) {
int u = Q.front (); Q.pop ();
cnt++;
for (int i=0; i<G[u].size (); ++i) {
int v = G[u][i];
if (!(--in[v])) Q.push (v);
}
}
if (cnt == n) return false;
else return true;
} int main(void) {
int T, cas = 0; scanf ("%d", &T);
while (T--) {
scanf ("%d", &n);
for (int i=1; i<=n; ++i) G[i].clear ();
for (int i=1; i<=n; ++i) {
scanf ("%s", s[i] + 1);
for (int j=1; j<=n; ++j) {
if (s[i][j] == '1') G[i].push_back (j);
}
} printf ("Case #%d: %s\n", ++cas, (Topo_Sort () ? "Yes" : "No"));
} return 0;
}
代码(DFS)：
/************************************************
* Author :Running_Time
* Created Time :2015-8-25 9:44:18
* File Name :E.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 2e3 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
char s[N][N];
bool vis[N];
int d[N];
int n; bool DFS(int u) {
for (int i=1; i<=n; ++i) {
if (s[u][i] == '1') {
if (vis[i] && d[u] == d[i] + 2) return true;
else if (!vis[i]) {
vis[i] = true; d[i] = d[u] + 1;
if (DFS (i)) return true;
}
}
}
return false;
} int main(void) {
int T, cas = 0; scanf ("%d", &T);
while (T--) {
scanf ("%d", &n);
memset (vis, false, sizeof (vis));
memset (d, 0, sizeof (d));
for (int i=1; i<=n; ++i) {
scanf ("%s", s[i] + 1);
} vis[1] = true;
printf ("Case #%d: %s\n", ++cas, (DFS (1) ? "Yes" : "No"));
} return 0;
}