题解：CF1217D Coloring Edges

题解：CF1217D Coloring Edges

前言

题目传送门

思路讲解

一共两种情况：

1. 无环，那么很简单，直接全部输出1即可
2. 有环，那么需要多种颜色

如果这个图中有环，那么对于这个环的路径，就有两种：

1. 大编号节点到小编号节点
2. 小编号节点到大编号节点

多构造几组数据后我们会发现：最多只需要两种颜色就能解决这个问题

对于情况二，每个环小编号到大编号的路径，我们都可以用颜色1，对于大编号到小编号的路径，我们都可以用颜色2。

那么，对于情况一，我们只需要输出1即可。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> g[10005];
int n, m, son[10005], ans[10005];
queue<int> q; // 拓扑排序的队列
inline bool check() // 检查是否存在环（拓扑排序）
{int cnt = 0; // 不在环中的节点数for (int i = 1; i <= n; i++) // 入队{if (!son[i]){q.push(i);cnt++;}}while (!q.empty()){int now = q.front();q.pop();for (auto y : g[now]) // 遍历其的所有出边{if (--son[y] == 0) // 入队{q.push(y);cnt++; // 这个节点也不在环中}}}return cnt != n;
}
signed main()
{cin >> n >> m; // 输入for (int i = 1; i <= m; i++){int u, v;cin >> u >> v;if (u < v) ans[i] = 1; // 小编号到大编号else ans[i] = 2; // 大编号到小编号g[u].push_back(v);son[v]++;}if (check()) // 有环{cout << "2\n";for (int i = 1; i <= m; i++) cout << ans[i] << " ";}else // 无环{cout << "1\n";for (int i = 1; i <= m; i++) cout << 1 << " ";}return 0;
}