1 条题解
-
0
#include <algorithm> #include <cstdio> #include <cstring> #include <vector> #define INF 1e9 using namespace std; struct edge { int v, w; bool operator<(const edge& a) const { return v < a.v || (v == a.v && w < a.w); } }; vector<edge> e[100005]; int dis[100005], vis[100005], ans, res, cnt, maxv, minv; int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); } void dfs(int u, int d) { if (dis[u]) { ans = gcd(ans, abs(d - dis[u])); return; } dis[u] = d, vis[u] = 1; maxv = max(maxv, dis[u]); minv = min(minv, dis[u]); for (auto i : e[u]) dfs(i.v, d + i.w); } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); e[u].push_back({v, 1}); e[v].push_back({u, -1}); } for (int i = 1; i <= n; i++) if (!vis[i]) { maxv = -INF, minv = INF; dfs(i, 1); res += maxv - minv + 1; } if (ans) { if (ans < 3) puts("-1 -1"); else for (int i = 3; i <= ans; i++) if (ans % i == 0) { printf("%d %d\n", ans, i); break; } } else { if (res < 3) puts("-1 -1"); else printf("%d 3\n", res); } return 0; }
- 1
信息
- ID
- 1064
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 13
- 已通过
- 3
- 上传者