506B

Description

There are $n$ vertexes in the graph. Now we need to add some unidirected edges to it. To make sure that we can go from $a$ to $b$ in each pair $(a,b)$ among the $m$ pairs given below. ($1 \leq n,m \leq 10^5$) Output the minimum number of edges to be added.

Tutorial

First we add all the edges and use Disjoint Set Union to see the connected components. In a component without circles, we can construct the edges like this. We arrange all the points in a line, and connect them into a chain. There must exist a chain can fulfill the condition in the description.

For those component contain circles, we just form a big circle which every vertex can go to every vertex.

Topological order can be used for circle detection. If after the BFS, there still some vertex's degree is not zero, it must contain cricle.

Solution

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

#define D(x) x

const int MAX_N = (int)(1e5) + 10;

struct DSU
{
    int father[MAX_N];

    DSU()
    {}

    DSU(int n)
    {
        for (int i = 0; i < n; i++)
        {
            father[i] = i;
        }
    }

    int find(int a)
    {
        int ret = a;
        while (father[ret] != ret)
            ret = father[ret];
        while (father[a] != a)
        {
            int b = a;
            a = father[a];
            father[b] = ret;
        }
        return ret;
    }

    void merge(int a, int b)
    {
        father[find(a)] = father[find(b)];
    }
};


int n, m;
bool circle[MAX_N];
vector<int> edge[MAX_N];
int degree[MAX_N];

void add_edge(int a, int b)
{
    edge[a].push_back(b);
    degree[b]++;
}

void bfs(int node_num, vector<int> edge[])
{
    //indexes start from 0
    queue<int> q;
    for (int i = 0; i < node_num; i++)
    {
        if (degree[i] == 0)
        {
            q.push(i);
        }
    }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        //push u into an array to get the topological order sequence
        for (int i = 0; i < (int)edge[u].size(); i++)
        {
            int v = edge[u][i];
            if (degree[v] == 0)
            {
                continue;
            }
            degree[v]--;
            if (degree[v] == 0)
            {
                q.push(v);
            }
        }
    }
    //if degree[i] != 0 now, it means there is a circle on the connected component with vertex i.
}

int main()
{
    //input
    scanf("%d%d", &n, &m);
    DSU dsu = DSU(n);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        a--;
        b--;
        add_edge(a, b);
        dsu.merge(a, b);
    }
    bfs(n, edge);
    for (int i = 0; i < n; i++)
    {
        if (degree[i])
        {
            circle[dsu.find(i)] = true;
        }
    }
    int ans = n;
    for (int i = 0; i < n; i++)
    {
        if (dsu.father[i] == i && !circle[i])
        {
            ans--;
        }
    }
    printf("%d\n", ans);
    return 0;
}