好烦，感觉自己的图论知识都有了，但是一旦写起来还是非常欠缺……
什么时候我才能踩完所有的坑，成就大佬之路呢……
今天多校的第二道签到题……
是的，签到题……但是我没有写出来为什么呢……我也想知道为什么我老是会这样那样的地方写错……
今天错的地方是没有去重，还像条疯狗一样跑去BC官方博客理论了……
在这里先道个歉……
但是题解的确没写清楚
题意：
给你一个有向图，有环，无重边，无自环。
问你是否存在两个不联通的点。
思路：
拿到题的第一思路，拓扑排序，有环就缩点呗！
然后开始疯狂WA……
思路没错，但是在缩点后没有去重，导致缩点后一条边的出度增加，拓扑排序失败……
好烦……讲道理缩点+拓扑，虽然简单，但也没有沦落到这种比赛的签到题上……
原因就是数据很小，允许 ( O ( n^2 ) )解题……
可能因为图论学傻了，没想到也不愿意用暴力做……
暴力的方法是，枚举每一个点，记录它可以达到的点，构成一个二维矩阵，然后遍历一下矩阵，看是否存在相互不可达的点即可。
虽然暴力在我眼里有点不齿，但是优雅的暴力还是非常值得认可的。
缩点 + 拓扑排序 AC Code
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1005;
int idx, n, m, scc, top, vis_time;
int head[maxn], dfn[maxn], low[maxn], in[maxn], color[maxn], st[maxn];
bool instack[maxn];
struct node {
int to;
int nxt;
} edges[7000];
bool g[maxn][maxn];
int deg[maxn];
int vex[maxn];
bool toposort()
{
for (int i = 1; i <= scc; i++)
for (int j = 1; j <= scc; j++)
g[i][j] = false;
for (int u = 1; u <= n; u++) {
int cu = color[u];
for (int id = head[u]; ~id; id = edges[id].nxt) {
int cv = color[edges[id].to];
if (cu != cv && !g[cu][cv]) { //这里要去重！！！
deg[cv]++;
g[cu][cv] = true;
}
}
}
queue<int> que;
for (int i = 1; i <= scc; i++)
if (deg[i] == 0)
que.push(i);
while (!que.empty()) {
if (que.size() > 1)
return true;
int u = que.front();
que.pop();
for (int i = 1; i <= scc; i++) {
if (g[u][i]) {
if (--deg[i] == 0)
que.push(i);
}
}
}
return false;
}
void addEdge(int u, int v)
{
edges[idx].to = v;
edges[idx].nxt = head[u];
head[u] = idx++;
}
void tarjan(int u)
{
int v;
low[u] = dfn[u] = ++vis_time;
instack[u] = true;
st[++top] = u;
for (int id = head[u]; ~id; id = edges[id].nxt) {
v = edges[id].to;
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (instack[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
scc++;
do {
v = st[top--];
instack[v] = false;
color[v] = scc;
} while (v != u);
}
}
void init()
{
for (int i = 0; i <= n; i++) {
head[i] = -1;
deg[i] = in[i] = dfn[i] = low[i] = 0;
}
vis_time = top = idx = scc = 0;
}
int main()
{
int T, u, v;
scanf("%d", &T);
while (T--) {
scanf("%d %d", &n, &m);
init();
while (m--) {
scanf("%d %d", &u, &v);
addEdge(u, v);
}
for (int i = 1; i <= n; i++)
if (dfn[i] == 0)
tarjan(i);
if (toposort())
puts("Light my fire!");
else
puts("I love you my love and our love save us!");
}
return 0;
}