字符串同构，tarjan，hash

题意：

分析：

不难想到用tarjan算法，将互相愿意组队的人员划分出来。但是，稍微有困难把你的便是：如何计算这只队伍的团结系数呢？

这里牵扯到了一个知识点：字符串同构！！
对于字符串a,和字符串b我们知道a经过一定的循环就会变成b。我们称a与b同构。
那么倘若我们将a,b都变为其最小的同构字符串c。
然后我们统计又多少人是同构字符串时，直接用hash表统计c的个数不就好了吗？

关键是如何变为最小的同构字符串呢？
这里给出代码：

string getmin(string s) {
    int len = s.size();int i = 0, j = 1, k = 0;
    while(i < len && j < len && k < len) {
        if (s[(i + k) % len] == s[(j + k) % len])k++;
        else if (s[(i + k) % len] > s[(j + k) % len])i = i + k + 1, k = 0;
        else if (s[(i + k) % len < s[(j + k) % len]])j = j + k + 1, k = 0;
        if (i == j)j++;
    }return (s + s).substr(min(i, j), len);
}

简单的说一下：上面又三个指针：i,j,k
分别意味着从i开始的同构字符串，从j开始的同构字符串，k就是个长度。

那么我们在每一个训话中比较的就是s[i+k],s[j+k]
即是以i开始的同构字符串和以j开始的同构字符串比较第k位。
如果第k位相等，那么k++我们比较k+1位

如果s[i+k]>s[j+k]那么我们知道了以i开始的字符串绝对不是最小同构字符串！
但是，同时我们还知道了以i+1,i+2,i+3。。。。。。i+k开始的同构字符串都不是最小字符串！
为什么这样呢？
我们假设从i+h开始，0<=h<=k
那么他一定比j+h的大，因为s[i+k]>s[j+k]啊
对不对，很简单？不难理解的。
然后这时我们就让i=i+k+1,k=0再次开始重新比较吧！

j也一样。当然我如果j==i了j++.否则就不能再比较了。
最后输出min(i,j)为什么是min(i,j)呢？
语言不大好表达，自己思考思考。当然记住也不难

如此，此题得解！！

代码如下：

#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<stack>
using namespace std;
const int max_n = 1e5 + 100;
const int max_m = 1e5 + 100;
int n, m;
string ss[max_n];

string getmin(string s) {
    int len = s.size();int i = 0, j = 1, k = 0;
    while(i <= len && j <= len && k <= len) {
        if (s[(i + k) % len] == s[(j + k) % len])k++;
        else if (s[(i + k) % len] > s[(j + k) % len])i = i + k + 1, k = 0;
        else if (s[(i + k) % len < s[(j + k) % len]])j = j + k + 1, k = 0;
        if (i == j)j++;
    }return (s + s).substr(min(i, j), len);
}

struct edge
{
    int to, next;
}E[max_n];
int head[max_n];
int cnt = 1;
void add(int from, int to) {
    E[cnt].to = to;
    E[cnt].next = head[from];
    head[from] = cnt++;
}

int res = 0;
stack<int> st;
int dfn[max_n], low[max_n], color[max_n];
int colour = 0, tot = 0;
map<string, int> mp;
void tarjan(int u) {
    dfn[u] = low[u] = ++tot;st.push(u);
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (!dfn[v]) { tarjan(v);low[u] = min(low[u], low[v]); }
        else if (color[v] == 0)low[u] = min(low[u], dfn[v]);
    }if (dfn[u] != low[u])return;
    colour++;
    while (st.top() != u) {
        color[st.top()] = colour;
        mp[ss[st.top()]]++;
        st.pop();
    }color[st.top()] = colour;mp[ss[st.top()]]++;st.pop();
    for (auto it = mp.begin();it != mp.end();it++)
        res = max(res, (*it).second);
    mp.clear();
}

void solve() {
    for (int i = 1;i <= n;i++)
        if (!dfn[i])tarjan(i);
    cout << res << endl;
}
void init() {
    fill(head, head + n + 10, false);
    cnt = 1;colour = 0;tot = 0;res = 0;
    fill(dfn, dfn + +n + 10, false);
    fill(color, color + n + 10, 0);
    fill(low, low + n + 10, 0);
}

int main() {
    ios::sync_with_stdio(0);
    while (cin >> n >> m) {
        init();
        for (int i = 1;i <= n;i++) {
            cin >> ss[i];
            ss[i] = getmin(ss[i]);
        }for (int i = 1;i <= m;i++) {
            int u, v;cin >> u >> v;
            add(u, v);
        }solve();
    }
}