本文共 4159 字，大约阅读时间需要 13 分钟。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6165

题意：一张有向图，n个点，m条边，保证没有重边和自环。询问任意两个点能否满足任何一方能够到达另外一方。

思路：枚举每个点，预处理搜出与这个点相连接的所有点，看看能不能搜出一条链出来，当然要注意一种情况，u-v，v-u这种也是可行的，特殊处理一下。

代码DFS：

#include
   
    using namespace std;const int maxn=1005;vector
    
     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
    
   

BFS

#include
   
    using namespace std;const int maxn = 1005;bool vis[maxn], dis[maxn][maxn];vector
    
     edge[maxn];int n, m, pos;void BFS(int u){
       queue
     
      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 
   
    using namespace std;const int maxn = 2005;int dfn[maxn];//dfs顺序int low[maxn];int index1;//记录时间的标号bool state[maxn];//是否在栈里.stack
    
     s;vector
     
      G[maxn];vector
      
       g[maxn];int cnt[maxn];int num[maxn], du[maxn];//num数组不一定要，各个强连通分量包含点的个数，数组编号1~cntint 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
       
        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
        
         =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
        
       
      
     
    
   

转载地址：https://dh-butterfly.blog.csdn.net/article/details/77484384 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！