506B


  Posted on 19 Jan 2015
dsu graphs

Description


There are vertexes in the graph. Now we need to add some unidirected edges to it. To make sure that we can go from to in each pair among the pairs given below. () 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;
}