Codeforces 183C（有向图上的环长度）

因为公用一个系统所以大家求gcd；衡量各点之间的拓扑位置，如果到达同一点有不同的长度则取gcd。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, ans;
int val[maxn];
vector<int> adj[maxn], len[maxn];
bool vis[maxn];
int gcd(int a, int b) {
if (!a || !b)
return a + b;//ans初始为0所以有此写法
return gcd(b, a % b);
}
void dfs(int cur, int id) {
vis[cur] = 1;
val[cur] = id;
for (int i = 0; i < adj[cur].size(); i++) {
int son = adj[cur][i], l = len[cur][i];
if (!vis[son]) {
dfs(son, id + l);
} else if (val[son] != id + l) {//到达同一点有不同长度
ans = gcd(ans, abs(id + l - val[son]));
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1, u, v; i <= m; i++) {
scanf("%d %d", &u, &v);
adj[u].push_back(v);
len[u].push_back(1);
//通过这种方式来计算两两点之间的拓扑相对位置
adj[v].push_back(u);
len[v].push_back(-1);
}
for (int i = 1; i <= n; i++)
if (!vis[i])
dfs(i, 0);
if (!ans)
ans = n;
return !printf("%dn", ans);
}