P2812

_Scaley · 2020-10-04 15:43:00 · 题解

我的第一篇题解~~

这个题大概是不难的 (:3 」∠)

题面概括

有一张有向图，给出点的数量n以及边的数量m，有两个问题：

problem1

至少选几个点开始搜索才能使整个图都能被遍历到

problem2

至少需要添加几条边能使整个图成为一个环？

题目分析

这个题的难点在于，我们不知道连接哪两座学校才能使整个图成为一个环，那么我们可以先把一些小问题完成再去看大问题（佛系）

一、tarjan缩点

从题目可以得知如果这个图中有环，那这个环中若有至少一个点可以被共享，整个环就可以被共享，这就可以把一个环看做成一个点，可以用tarjan缩点完成

二、对入度为0的点和出度为0的点进行操作

子问题1：入度为0的点

如果在所有入度为0的点上设母机，那么整个图都会被共享

这也是problem1的答案

然后我们可以知道，缩点后的图是一个有向无环图，每个点都有一个入度和出度，入度为0的点无法被共享，那我们要想办法让这种点入度不为0呐~肯定要连边使入度为0的点的入度不为0 （好绕）

子问题2：出度为0的点

这样的话问题又来了：如果随便找个点连接入度为0的点的话，那连接入度为0的那个点的出度是否为0？

如果出度不为0，那么从这个点出发的点就无法在这个环里，以它为母机，会有学校共享不到，所以出度为零的点也需要向外连一条边

分析结果

不难想到，让出度为0的点向入度为0的点连一条边

那答案就出来了：

problem1：

入度为0的点的个数

problem2：

max（入度为0的点的数量，出度为0的点的数量）:

注意：当只有一个点（或者强连通分量时），输出0！！！（这个可能会成为强化数据）

更详细的请见完整代码

完整AC代码

#include <iostream>
#include <cstdio>
#include <cmath>
#define MAXN 10010
using namespace std;

int vis[MAXN], head[MAXN];
int js = 0, n, m, op=0, cnt, top=0;
int sta[MAXN], low[MAXN], dfn[MAXN];
int num[MAXN], sum[MAXN], g=0, oq=0;//num[i]记录点i的序号，sum[i]记录序号为i的强连通分量的元素个数
int rd[MAXN],cd[MAXN];//记录入度和出度

struct edge{
    int v, nxt;
}e[5000010 << 1];

void addage(int u, int v){
    e[++js].v = v;
    e[js].nxt = head[u];
    head[u] = js;
}

void tarjan(int t){//tarjan缩点板子
    sta[++top] = t;
    vis[t] = 1;
    low[t] = dfn[t] = ++op;
    for (int j = head[t]; j; j = e[j].nxt){
        int v = e[j].v;
        if (!dfn[v]){
            tarjan(v);
            low[t] = min (low[t], low[v]);
        }
        else if (vis[v])
            low[t] = min (low[t], low[v]);
    }
    if (low[t] == dfn[t]){
        int f = sta[top--];
        vis[f] = 0;
        num[f] = ++g;
        sum[g]++;
        while (f != t){
            f = sta[top--];
            vis[f] = 0;
            num[f] = g;
            sum[g]++;
        }
    }
}

int main(){
    int x, y, v, ans=0, jss=0,mm;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        while (scanf("%d", &x)){
            if (x == 0) break;
            addage(i, x);
        }
    }//输入
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; i++){
        for (int j = head[i]; j; j = e[j].nxt){
            v = e[j].v;
            if (num[i] != num[v]){
                cd[num[i]]++;//记录每个点的入度
                rd[num[v]]++;//记录每个点的出度
            }
        }
    }
    for (int i = 1;i <= g; i++){
        if (!rd[i]){
            ans++;
        }//记录入度为0的点的数量
        if (!cd[i]){
            jss++;
        }//记录出度为0的点的数量
    }
    mm=max(ans,jss);//比较
    printf("%d\n%d\n",ans,mm);
    return 0;
}

求管理员大大让我过审吧！！(•ㅂ•)/♥