有向图的强连通分量

AcWing 1174. 受欢迎的牛

题目

https://www.acwing.com/problem/content/1176/ 每一头牛的愿望就是变成一头最受欢迎的牛。现在有 N 头牛，编号从 1 到 N，给你 M 对整数 (A,B)，表示牛 A 认为牛 B 受欢迎。这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。

思路

缩点：将每个强连通分量看作一个点，通过有向边将他们连接起来，得到一个有向无环图（DAG），也就是拓扑图。做完Tarjan算法后，进行缩点之后的强连通分量已经按照其编号递减的顺序完成拓扑序。既然强连通分量已完成拓扑排序，那么：

如果在这个拓扑图中至少存在两个点的出度为0（终点无后继），那么就不存在被除自己之外的所有牛认为是受欢迎的牛，至少有另外一个终点没有认为它受欢迎。
如果只存在一个点其出度为0，那么这个点所代表的强联通分量中的所有牛都是被除自己之外的所有牛认为是受欢迎的牛。因为在该强连通分量内部，所有点都是连通的；在该强连通分量外部，这种关系是具有传递性，最终会沿着拓扑序走到该强连通分量。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 10010, M = 50010;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, _size[N];
int dout[N];//记录每个连通分量的出度

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (in_stk[j]) {
            low[u]=min(low[u],dfn[j]);
        }
    }
    if (dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do {
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;//y元素所属的连通块编号
            _size[scc_cnt]++;//该连通块内包含的点数
        } while (y!=u);
    }
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    for (int i = 1; i <= n; ++i) {
        if (!dfn[i])
            tarjan(i);
    }

    // 统计在新图中所有点的出度
    for(int i=1;i<=n;i++){
        for(int j=h[i];~j;j=ne[j]){
            int k=e[j];
            int a=id[i],b=id[k];//a表示i所在连通分量的编号,b表示k所在连通分量的编号
            if (a!=b){ //如果点i和点k不在同一个连通块
                dout[a]++; // 从a走到b，a的出度++
            }
        }
    }
    // zeros是统计在新图中，出度为0的点的个数
    // sum表示满足条件的点（最受欢迎的奶牛）的个数
    int zeros=0,sum=0;
    for(int i=1;i<=scc_cnt;i++){
        if (!dout[i]){
            zeros++;
            sum+= _size[i];
            if (zeros>1){
                sum=0;
                break;
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}

AcWing 367. 学校网络

题目

一些学校连接在一个计算机网络上，学校之间存在软件支援协议，每个学校都有它应支援的学校名单（学校 A 支援学校 B，并不表示学校 B 一定要支援学校 A）。当某校获得一个新软件时，无论是直接获得还是通过网络获得，该校都应立即将这个软件通过网络传送给它应支援的学校。因此，一个新软件若想让所有学校都能使用，只需将其提供给一些学校即可。现在请问最少需要将一个新软件直接提供给多少个学校，才能使软件能够通过网络被传送到所有学校？最少需要添加几条新的支援关系，使得将一个新软件提供给任何一个学校，其他所有学校就都可以通过网络获得该软件？

思路

先进行缩点，得到有向无环图（DAG），也就是拓扑图，统计每个强连通分量的出（终点）入(起点)度问题一：

只需要把软件给所有起点即可，答案为入度：

问题二：

scc_cnt(强连通分量个数)==1,答案为0；
scc_cnt>1,答案为：max(入度,出度)

代码

#include <bits/stdc++.h>

using namespace std;

const int N=110,M=10010;

int n;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt;
int din[N],dout[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=true;

    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]= min(low[u],low[j]);
        }else if (in_stk[j])
            low[u]= min(low[u],dfn[j]);
    }
    if (dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do {
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
        } while (y!=u);
    }
}

int main() {
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
    {
        int t;
        while (cin>>t,t) add(i,t);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);

    for(int i=1;i<=n;i++)
    {
        for(int j=h[i];~j;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if (a!=b)
            {
                dout[a]++;
                din[b]++;
            }
        }
    }

    int a=0,b=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if (!din[i]) a++;
        if (!dout[i])b++;
    }
    cout<<a<<endl;
    if (scc_cnt==1) cout<<"0"<<endl;
    else cout<<max(a,b)<<endl;
    return 0;
}

AcWing 1175. 最大半连通子图

题目

https://www.acwing.com/problem/content/1177/

思路

半连通：一个点可以走到另一个点就是半连通

先用tarjan算法缩点，有向无环图（DAG），也就是拓扑图
然后根据缩点之后重新建图，建图时需要给边判重，防止在 $f[j]+s[i]==f[i]$ 的情况下,会 $g[i]+=g[j]$ 多次
最后在统计最长的链即可
- f[i]表示权重的最大值
- g[i]表示让f[i]最大的方案数
- s[i]表示强连通分量i结点数
- 如果f[j]+s[i]>f[i]:更新路径权重f[i]=f[j]+s[i],更新方案数：g[i]=g[j]
- 如果f[j]+s[i]==f[i]:只需要更新方案数g[i]+=g[j]

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 10, M = 2e6 + 10;

int n, m, mod;
int h[N], hs[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, scc_size[N];
int f[N], g[N];

void add(int h[], int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int y;
        do {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
            scc_size[scc_cnt]++;
        } while (y != u);
    }
}


int main() {
    cin >> n >> m >> mod;
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(h, a, b);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);

    unordered_set<LL> S;
    for (int i = 1; i <= n; i++)
        for (int j = h[i]; ~j; j = ne[j]) {
            int k = e[j];
            int a = id[i], b = id[k];
            LL hash = a * 1000000ll + b;
            if (a != b && !S.count(hash)) {
                add(hs, a, b);
                S.insert(hash);
            }
        }
    for (int i = scc_cnt; i; i--) {
        if (!f[i]) {
            f[i] = scc_size[i];
            g[i] = 1;
        }
        for (int j = hs[i]; ~j; j = ne[j]) {
            int k = e[j];
            if (f[k] < f[i] + scc_size[k]) {
                f[k] = f[i] + scc_size[k];
                g[k] = g[i];
            } else if (f[k] == f[i] + scc_size[k]) {
                g[k]=(g[k]+g[i])%mod;
            }
        }
    }
    int maxf=0,sum=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if (f[i]>maxf)
        {
            maxf=f[i];
            sum=g[i];
        }else if (f[i]==maxf) sum=(sum+g[i])%mod;
    }
    cout<<maxf<<endl;
    cout<<sum<<endl;
    return 0;
}

AcWing 1174. 受欢迎的牛​

题目​

思路​

代码​

AcWing 367. 学校网络​

题目​

思路​

代码​

AcWing 1175. 最大半连通子图​

题目​

思路​

代码​

AcWing 1174. 受欢迎的牛

题目

思路

代码

AcWing 367. 学校网络

题目

思路

代码

AcWing 1175. 最大半连通子图

题目

思路

代码