题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6165
题意：一张有向图，n个点，m条边，保证没有重边和自环。询问任意两个点能否满足任何一方能够到达另外一方。
思路：枚举每个点，预处理搜出与这个点相连接的所有点，看看能不能搜出一条链出来，当然要注意一种情况，u-v，v-u这种也是可行的，特殊处理一下。
代码DFS：
#include<bits/stdc++.h> using namespace std; const int maxn=1005; vector<int>edge[maxn]; bool vis[maxn],dis[maxn][maxn]; int n,m,pos; void dfs(int u) {vis[u]=true;dis[pos][u]=true;for(int i=0;i<edge[u].size();i++){int v=edge[u][i];if(vis[v]) continue;dfs(v);} } int main() {int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){edge[i].clear();}for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);edge[u].push_back(v);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j]=false;}}int flag=1;for(int i=1;i<=n;i++){memset(vis,false,sizeof(vis));pos=i;dfs(i);}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(dis[i][j]==false&&dis[j][i]==false){flag=0;break;}}}if(!flag) printf("Light my fire!\n");else printf("I love you my love and our love save us!\n");}return 0; }
BFS
#include<bits/stdc++.h> using namespace std; const int maxn = 1005; bool vis[maxn], dis[maxn][maxn]; vector<int>edge[maxn]; int n, m, pos; void BFS(int u) {queue<int>q;q.push(u);while(!q.empty()){int now=q.front();q.pop();if(vis[now]) continue;vis[now]=true;dis[pos][now]=true;for(int i = 0; i < edge[now].size(); i++){int v = edge[now][i];if(vis[v]) continue;q.push(v);}} } int main() {int T;scanf("%d", &T);while(T--){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) edge[i].clear();for(int i = 1; i <= m; i++){int u, v;scanf("%d%d", &u, &v);edge[u].push_back(v);}for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){dis[i][j] = false;}}for(int i = 1; i <= n; i++){memset(vis, false, sizeof(vis));pos = i;BFS(i);}int flag = 1;for(int i = 1; i <= n; i++){for(int j = i + 1; j <= n; j++){if(dis[i][j] == false && dis[j][i] == false){flag = 0;break;}}}if(!flag) puts("Light my fire!");else puts("I love you my love and our love save us!");}return 0;
}
tarjan代码：
tarjan学习：http://www.cnblogs.com/uncle-lu/p/5876729.html
思路：tarjan部分直接上模板，主要思路就是缩点成链之后进行拓扑排序，因为它要求的是任意两点任何一点能够到达另外一点，所以就如果入度为0的点的个数大于等于两个，那就是不满足的。
代码：
#include <bits/stdc++.h> using namespace std; const int maxn = 2005; int dfn[maxn];//dfs顺序 int low[maxn]; int index1;//记录时间的标号 bool state[maxn];//是否在栈里. stack<int>s; vector<int>G[maxn]; vector<int>g[maxn]; int cnt[maxn]; int num[maxn], du[maxn];//num数组不一定要，各个强连通分量包含点的个数，数组编号1~cnt int scc,flag;//scc为强连通分量的个数 int vis[maxn]; void init() {scc = 0,flag=0;memset(du, 0, sizeof(du));memset(state, false, sizeof(state));memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));memset(cnt, 0, sizeof(cnt));memset(vis, false, sizeof(vis));memset(num, 0, sizeof(num));while(!s.empty())s.pop();for(int i = 0; i < maxn; i++){G[i].clear();g[i].clear();} } void tarjan(int u)//tarjan 处理强连通分量。 {dfn[u] = low[u] = ++index1;s.push(u);state[u] = true;vis[u] = true;for(int i = 0; i < G[u].size(); i++){int w = G[u][i];if(!vis[w]){tarjan(w);low[u] = min(low[w], low[u]);}else if(state[w]){low[u] = min(low[u], dfn[w]);}}if(low[u] == dfn[u]){scc++;for(;;){int x = s.top();s.pop();cnt[x] = scc;//标记v点属于哪个强连通分量num[scc]++;//记录这个强连通分量有多少个点组成state[x] = false;if(x == u)break;}} } void topsort() {queue<int>q;int sizz=0;for(int i=1;i<=scc;i++){if(!du[i]){sizz++;q.push(i);}}if(sizz>=2) flag=1;//如果刚缩点后就有两个以上度为0的坑定不可以啊while(!q.empty()&&!flag){int u=q.front();q.pop();int siz=0;for(int i=0;i<g[u].size()&&!flag;i++){int to=g[u][i];du[to]--;if(du[to]==0){siz++;q.push(to);}if(siz>=2) flag=1;}if(flag) break;} } int main() {int T;scanf("%d",&T);while(T--){int n,m;scanf("%d%d",&n,&m);init();for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);}for(int i=1;i<=n;i++){if(!dfn[i]){tarjan(i);}}for(int i=1;i<=n;i++)//新建图{int u=cnt[i];for(int j=0;j<G[i].size();j++){int v=cnt[G[i][j]];if(u!=v){g[u].push_back(v);du[v]++;//入度}}}topsort();if(flag) puts("Light my fire!");else puts("I love you my love and our love save us!");}return 0; }
