题目链接:HDU - 6165
显然可以n次bfs,求连通性。但是时间卡得很紧。
这里我们可以 O(n+m)的复杂度解决。
先缩点变成DAG,然后缩点的图上跑Top,如果某一时刻,一个点可以让两个及以上的点度为0,那么显然就无解。否则有解。
AC代码:
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1010;
int n,m,deg[N];
int low[N],dfn[N],vis[N],scc[N],co,cnt; stack<int> s;
vector<int> g[N],v[N];
inline int init(){for(int i=1;i<=n;i++) dfn[i]=low[i]=deg[i]=scc[i]=0,g[i].clear(),v[i].clear(); cnt=co=0;
}
void Tarjan(int x){dfn[x]=low[x]=++cnt; vis[x]=1; s.push(x);for(auto to:g[x]){if(!dfn[to]) Tarjan(to),low[x]=min(low[x],low[to]);else if(vis[to]) low[x]=min(low[x],dfn[to]);}if(dfn[x]==low[x]){int u; co++;do{u=s.top(); s.pop(); scc[u]=co; vis[u]=0;}while(u!=x);}
}
void build_new_graph(){for(int i=1;i<=n;i++)for(auto to:g[i]) if(scc[i]!=scc[to]){v[scc[i]].push_back(scc[to]); deg[scc[to]]++;}
}
int Top(){queue<int> q; for(int i=1;i<=co;i++) if(!deg[i]) q.push(i);if(q.size()>=2) return 1;while(q.size()){int u=q.front(); q.pop(); int cnt=0;for(auto to:v[u]){if(--deg[to]==0) q.push(to),cnt++;}if(cnt>=2) return 1;} return 0;
}
inline void solve(){cin>>n>>m; init();for(int i=1,a,b;i<=m;i++) scanf("%d %d",&a,&b),g[a].push_back(b);for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i);build_new_graph();puts(Top()?"Light my fire!":"I love you my love and our love save us!");
}
signed main(){int T; cin>>T;while(T--) solve();return 0;
}