CF-1217D Coloring Edges 题解

题目大意

小明是一个国王，他的国家有n个城市。

现在小明想为这n个城市制造m条路径（路径都是有向的），现在小明有k种不同种类的材料，可以用来制造路径。

无自环，无重复边。

在制造路径的时候，小明不想看到一个环的路径都是由一种材料制造成的，这样小明就会生气。

现在问你这个k最小值应该是多少呢。

解题思路

（来补一下题解

题目的要求是每个环的路径的材料不能完全相同，那么我们可以将不是环的点的k值赋为1，在环中的最多也是2。

那么存在环k最大为2，不存在则k为1。

首先，我们可以使用拓扑排序来判环。

（写这题之前完全就没听过。。

判断是否有环之后，如果不存在环，则每个点都为1。

如果存在环，那么可以用dfs来在环内赋值。

有一个很巧妙的方法来赋值。

（我也是看到了别人的题解才想到的。。

就是如果这个点比其他点大，就赋为1，否则赋为2。

显然，在一个环中，是不可能出现单增或者单降的，所以整个环必然不可能是同一种颜色。

完整代码

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

vector<int>Map[5050];
queue<int>q, p;
int ans[5050][5050];
int l[5050], r[5050], in[5050], mark[5050];

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> l[i] >> r[i];
		Map[l[i]].push_back(r[i]);
		in[r[i]]++;
		ans[l[i]][r[i]] = 1;
	}
	for (int i = 1; i <= n; i++) {//拓扑排序
		if (!in[i]) {
			mark[i] = 1;
			q.push(i);
		}
	}
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		p.push(node);
		for (auto it = Map[node].begin(); it != Map[node].end(); it++) {
			in[*it]--;
			if (!in[*it]) {
				mark[*it] = 1;
				q.push(*it);
			}
		}
	}
	int flag = 0;
	if (p.size() == n)	flag = 1;//判断是否有环
	else {
		for (int i = 1; i <= n; i++) {
			if (!mark[i]) {
				q.push(i);				
				while (!q.empty()) {
					int m = q.front();
					q.pop();
					mark[m] = 1;
					for (auto it = Map[m].begin(); it != Map[m].end(); it++) {
						if (m > (*it))	ans[m][*it] = 1;
						else ans[m][*it] = 2;
						if(!mark[*it])	q.push(*it);
					}
				}

			}
		}
	}
	if (flag)	cout << 1 << endl;
	else cout << 2 << endl;
	for (int i = 0; i < m; i++) {
		cout << ans[l[i]][r[i]];
		if (i != m - 1)	cout << " ";
		else cout << endl;
	}
}