hdu6165 FFF at Valentine 2017多校第九場1005 dfs

http://acm.split.hdu.edu.cn/showproblem.php?pid=6165

題意：給出一個有向圖，要求圖上任意兩點是可達的(不需要互相可達)

題解：dfs，每次搜尋每個結點的兒子然後标記連通即可。

代碼：

#include<bits/stdc++.h>
#define debug cout<<"aaa"<<endl
#define d(a) cout<<a<<endl
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define MIN_INT (-2147483647-1)
#define MAX_INT 2147483647
#define MAX_LL 9223372036854775807i64
#define MIN_LL (-9223372036854775807i64-1)
using namespace std;

const int N = 1000 + 5;
const int mod = 1000000000 + 7;
const double eps = 1e-8;
int dp[N][N];//可達标記 
bool vis[N];
vector<int> son[N];

void dfs(int u,int fa){
	dp[fa][u]=vis[u]=1;//記為可達 
	for(int i=0;i<son[u].size();i++){
		int v=son[u][i];
		if(!vis[v]){
			dfs(v,fa);
		}
	}
}

int main(){
	int t,m,n,u,v;
	bool flag;
	scanf("%d",&t);
	while(t--){
		flag=1,mem(dp,0),mem(vis,0);
		scanf("%d%d",&n,&m);
		for(int i=0;i<=n;i++){
			son[i].clear();
		}
		for(int i=1;i<=m;i++){
			scanf("%d%d",&u,&v);
			dp[u][v]=1;
			son[u].push_back(v);
		}
		for(int i=1;i<=n;i++){
			vis[i]=1;
			dfs(i,i);
			mem(vis,0);
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<i;j++){
				if(dp[i][j]||dp[j][i]) continue;
				flag=0;
			}
		}
		if(flag){
			puts("I love you my love and our love save us!");
		}
		else{
			puts("Light my fire!");
		}
	}
	return 0;
}