HDU 4324 Triangle LOVE(拓扑排序)

HDU 4324 Triangle LOVE(拓扑排序)

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

题意:给你一个特殊的有向图,该有向图的任意两个节点u与v之间有且仅有一条单向边,现在问你该有向图是否存在由3个节点构成的环.

分析:

该图本质是拓扑排序题.如果该图可以拓扑排序,那么不存在3节点的环,否则存在3节点的环.下面是证明:

首先存在3节点的环-> 不能拓扑排序.

其次我们现在证明 不能拓扑排序->存在3节点的环.

假设图不能拓扑排序,那么该图一定存在一个n节点(n>=3)的环.假设该环为a->b->c->d->….. 等. 由于a与c之间必然存在边,所以如果此边为c->a,那么就存在3节点环了.否则此边为a->c的话,那么a->c->d->…构成了一个n-1节点的环.依次类推,我们可以有n节点的环得出该图必然存在n-1,n-2,…一直到3节点的环.

所以能拓扑排序 <==> 不存在3节点环.

AC代码: (读输入的时候,如果一次读一个字符会超时)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=2000+10;
int n;
vector<int> G[maxn];
int in[maxn];
bool topo()
{
    queue<int> Q;
    for(int i=0;i<n;i++)
        if(!in[i]) Q.push(i);
    int sum=0;
    while(!Q.empty())
    {
        int u=Q.front(); Q.pop();
        sum++;
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];
            if(--in[v]==0) Q.push(v);
        }
    }
    return sum==n;
}
int main()
{
    int T; scanf("%d",&T);
    for(int kase=1;kase<=T;kase++)
    {
        scanf("%d",&n);
        memset(in,0,sizeof(in));
        for(int i=0;i<n;i++)
        {
            G[i].clear();
            char str[maxn];
            scanf("%s",str);
            for(int j=0;j<n;j++)if(str[j]=='1')
            {
                G[i].push_back(j);
                in[j]++;
            }
        }
        printf("Case #%d: %s\n",kase,topo()?"No":"Yes");
    }
    return 0;
}