Problem Description
At Valentine’s eve, Shylock and Lucar were enjoying their time as any other couples. Suddenly, LSH, Boss of FFF Group caught both of them, and locked them into two separate cells of the jail randomly. But as the saying goes: There is always a way out , the lovers made a bet with LSH: if either of them can reach the cell of the other one, then LSH has to let them go.
The jail is formed of several cells and each cell has some special portals connect to a specific cell. One can be transported to the connected cell by the portal, but be transported back is impossible. There will not be a portal connecting a cell and itself, and since the cost of a portal is pretty expensive, LSH would not tolerate the fact that two portals connect exactly the same two cells.
As an enthusiastic person of the FFF group, YOU are quit curious about whether the lovers can survive or not. So you get a map of the jail and decide to figure it out.
Input
[Math Processing Error]Input starts with an integer T (T≤120), denoting the number of test cases.
[Math Processing Error]For each case,
First line is two number n and m, the total number of cells and portals in the jail.(2≤n≤1000,m≤6000)
Then next m lines each contains two integer u and v, which indicates a portal from u to v.
Output
If the couple can survive, print “I love you my love and our love save us!”
Otherwise, print “Light my fire!”
Sample Input
3
5 5
1 2
2 3
2 4
3 5
4 5
3 3
1 2
2 3
3 1
5 5
1 2
2 3
3 1
3 4
4 5
Sample Output
Light my fire!
I love you my love and our love save us!
I love you my love and our love save us!
思路
给定一张有向图，是否有一个点能够到达所有点，包括间接到达也算。那么简单一点想就是排成一条长长队的一个序列。利用Tarjan缩点，缩完点之后就变成了一张有向无环图(DAG)。然后跑一次拓扑排序，如果拓扑序有解并且拓扑序列唯一那么就能解救。
-
拓扑序列有解的情况就是所有出队点的数目等于给定点的数目
-
拓扑序列唯一的条件是 条件1成立并且 每次出队之前队列里有且只有一个元素。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
const int maxn = 1005;
const int maxm = 6005;
struct edge{
int from;
int to;
int next;
}e[maxm<<1];
int tot,cnt,res;
vector<int>v[maxn]; //缩点建图
int head[maxn];
int scc[maxn]; //强连通编号
int dfn[maxn]; //时间戳
int low[maxn]; //最小返祖编号
int d[maxn]; //度
stack<int>s;
inline void addedge(int x,int y)
{
e[tot].from = x;
e[tot].to = y;
e[tot].next = head[x];
head[x] = tot++;
}
inline void clear_set()
{
tot = cnt = res = 0;
memset(head,-1,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(scc,0,sizeof(scc));
memset(d,0,sizeof(d));
while(!s.empty()) s.pop();
for(int i = 0;i < maxn;i++){
v[i].clear();
}
}
void tarjan(int x) //深搜访问
{
dfn[x] = low[x] = ++cnt;
s.push(x); //压栈
for(int i = head[x];~i;i = e[i].next){
int y = e[i].to;
if(!dfn[y]){ //这个点没有访问过
tarjan(y);
low[x] = min(low[x],low[y]);
}
else if(!scc[y]){
low[x] = min(low[x],dfn[y]);
}
}
if(low[x] == dfn[x]){ //这里就是一个强连通
res++;
while(true){
int p = s.top();
s.pop();
scc[p] = res; //p点属于res这个强连通编号
if(p == x) break;
}
}
}
int topsort()
{
queue<int>q;
for(int i = 1;i <= res;i++){
if(!d[i]){
q.push(i);
}
}
int f = 1,num = 0;
while(!q.empty()){
if(q.size() > 1){ //序列不唯一，无解
f = 0;
break;
}
int x = q.front();
q.pop();
num++; //这里判断有无解
for(int i = 0;i < v[x].size();i++){
int y = v[x][i];
d[y]--;
if(!d[y]){
q.push(y);
}
}
}
return num == res && f == 1;
}
int main()
{
int t,n,m;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
clear_set();
int x,y;
for(int i = 0;i < m;i++){
scanf("%d%d",&x,&y);
addedge(x,y);
}
for(int i = 1;i <= n;i++){
if(!dfn[i]){
tarjan(i);
}
}
for(int i = 0;i < tot;i++){
x = e[i].from; //有向边i的起点属于哪个scc
y = e[i].to; //有向边i的终点属于哪个scc
if(scc[x] != scc[y]){ //不是同一个scc建立拓扑图
d[scc[y]]++;
v[scc[x]].push_back(scc[y]);
}
}
int ans = topsort();
if(ans){
printf("I love you my love and our love save us!\n");
}
else{
printf("Light my fire!\n");
}
}
return 0;
}
愿你走出半生，归来仍是少年~
更多推荐
HDU6165(FFF at Valentine)
发布评论