M_sea

洛谷2746 校园网Network of Schools
Luogu算法Tarjan。首先跑一遍Tarjan,顺便缩点。然后统计入度为$0$和出度为$0$的点的个数,记为$...
扫描右侧二维码阅读全文
23
2017/10

洛谷2746 校园网Network of Schools

Luogu

算法

Tarjan。

首先跑一遍Tarjan,顺便缩点。

然后统计入度为$0$和出度为$0$的点的个数,记为$ansi$和$anso$。
第一问的答案即$ansi$,第二问的答案为$max(ansi,anso)$。

附一段证明:

对于任务A,我们只需要输出入度为0的点数——因为我们从这些点开始走就能走遍整个图,即满足任务A。对于任务B,如果出度为0的点更多,我们只要把所有出度为0的点连到入度为0的点上即可。如果入度为0的点更多,那么就要把一些多出来的入度为0的点连进图——即输出$max(ansi,anso)$。

当然,要注意特判原图就是强连通图的情况,此时答案应为1 0

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <stack>
#define re register
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;
}
struct Edge { int v,nxt; }e[10010];
int head[110],cnt;
inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int dfn[110],low[110],belong[110];
bool vis[110];
stack<int> st;
int dfs_clock=0,node_num=0;
inline void Tarjan(int u) { //Tarjan缩点
    dfn[u]=++dfs_clock; low[u]=dfn[u];
    st.push(u); vis[u]=true;
    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 (vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if (low[u]==dfn[u]) {
        node_num++; int v;
        do {
            v=st.top();
            belong[v]=node_num;
            vis[v]=false; st.pop();
        } while (v!=u);
    }
}
int ide[110],ode[110]; //缩完点后的入度和出度
int main() {
    int n=read();
    for (re int i=1;i<=n;i++) { //建图
        int v=read();
        while (v!=0) { addEdge(i,v); v=read(); }
    }
    for (re int i=1;i<=n;i++) //跑Tarjan
        if (!dfn[i]) Tarjan(i);
    for (re int i=1;i<=n;i++) //计算入度和出度
        for (re int j=head[i];j;j=e[j].nxt) {
            if (belong[i]!=belong[e[j].v]) {
                ode[belong[i]]++;
                ide[belong[e[j].v]]++;
            }
        }
    int ansi=0,anso=0;
    for (re int i=1;i<=node_num;i++) { //统计
        if (!ide[i]) ansi++;
        if (!ode[i]) anso++;
    }
    if (node_num==1) printf("1\n0\n"); //特判
    else printf("%d\n%d\n",ansi,max(ansi,anso));
    return 0;
}
最后修改:2019 年 05 月 26 日 02 : 20 PM

发表评论