洛谷2341 [HAOI2006]受欢迎的牛

Luogu

算法

有两个性质:

在有向图中,如果有且仅有一个点的出度为0,那么该点可以被所有点遍历到;反之,该图中没有可以被所有点遍历到的点。

在有向图中,如果一个点可以被所有点遍历到,那么这个点的出度为0。

但是这个题可能有环,或者别的奇奇怪怪的东西

那么Tarjan缩个点就好了。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
#define max_(a,b) ((a)>(b)?(a):(b))
#define min_(a,b) ((a)<(b)?(a):(b))
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,m;

int x[50010],y[50010];
struct Edge { int v,nxt; };
Edge e[50010];
int head[10010],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int dfn[10010],low[10010],dfs_clock=0;
int belong[10010],sum[10010],tot=0;
int sta[10010],in_stack[10010],top=0;

inline void Tarjan(int u) {
    dfn[u]=low[u]=++dfs_clock;
    sta[++top]=u; in_stack[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) {
            Tarjan(v);
            low[u]=min_(low[u],low[v]);
        }
        else if (in_stack[v]) low[u]=min_(low[u],dfn[v]);
    }
    if (dfn[u]==low[u]) {
        ++tot; re int now;
        while (1) {
            now=sta[top--];
            belong[now]=tot;
            sum[tot]++;
            in_stack[now]=0;
            if (now==u) break;
        }
    }
}

int degree[10010];

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        x[i]=read(),y[i]=read();
        addEdge(x[i],y[i]);
    }
    for (re int i=1;i<=n;++i)
        if (!dfn[i]) Tarjan(i);
    for (re int i=1,u,v;i<=m;++i) {
        u=x[i],v=y[i];
        if (belong[u]!=belong[v]) ++degree[belong[u]];
    }
    re int ans=0,s=0;
    for (re int i=1;i<=tot;++i)
        if (!degree[i]) ++s,ans+=sum[i];
    if (s>1) putchar('0'),putchar('\n');
    else printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 20 PM

发表评论