团结就是力量 -强连通分量+最小表示

本文主要是介绍团结就是力量 -强连通分量+最小表示，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/problem/14411
来源：牛客网

题目描述

从小老师就教育我们，一根筷子容易折断，而一捆筷子不容易折断。
因为要出战世界杯，我们需要考虑派一只队伍出战，而我们希望出战的队伍的团结力最大。
而一个队伍的团结力取决于每个人的性格，每个人都有一个性格基因【（由字符串表示），比如小明的性格基因为：abbcde】，性格基因的排列方式是可以通过一个人的后天培养而改变的，其改变方式就是类似于循环，【小明的性格基因为：abbcde，他可以变成：bbcdea，bcdeab，cdeabb，deabbc，eabbcd】。
一个队伍中如果最多有x个人的性格基因可以完全相等的话，那么这个队伍的团结力就是x。
比如一个队伍有五个人：
小明：abbcde
小红：bbcdea
大明：cdeabb
大红：efg
小紫：fge
明显小明小红和大明的性格基因可以变成相等的，大红和小紫的性格基因可以变成相等的，这个最多有3个人的性格基因可以完全相等的，所以这个五人队伍的团结力就是3；

现在已知可以出战的人数为n个，每个人都有一个性格基因字符串，而作为一只队伍出战的话，需要队伍中的每个人都互相达成共识。同时也已知m个信息，每个信息是：
a想要和b一起出战【注意，这里只是a的一厢情愿】，只有当a想要和b一起出战，并且b也想要和a一起出战的时候，两个人才能一起出战。想要一起出战是可以具有传递性的，比如a想要和b一起出战，b想要和c一起出战的话，那么a也可以想要和c一起出战。

我们肯定希望派出的队伍的团结力最大，请计算出这个最大团结力。

输入描述

本题包含多组数据，第一行输入两个数字n，m，分别表示一共有n个人，以及m个出战信息 。
接下来n行，每行输入一个字符串，表示每个人的性格基因。
再接下来m行，每行两个编号x，y，表示x想要和y出战
数据范围：
5<=n<=100000
1<=m<=100000
1<=x,y<=n
每个数据的字符串长度和不超过100000

输出描述

每组数据输出一行，表示最大团结力。

分析

这个题思路比较简单，求每个强连通分量内的团结力即可
我们可以把所有循环顺序内字典序最小的记录下来，然后用map存一下，记录最大值即可

代码

#include <iostream>
#include <cstring>
#include <stack>
#include <string>
#include <map>using namespace std;const int N = 100010,M = 200010;
int h[N],ne[M],e[M],idx;
int dfn[N],low[N],ti;
int id[N];
stack<int> Q;
bool in_st[N];
int scc_cnt;
int Size[N];
string str[N];
int n,m;
int ans;void add(int a,int b){ne[idx] = h[a],e[idx] = b,h[a] = idx++;
}void tarjan(int u){dfn[u] = low[u] = ++ti;Q.push(u),in_st[u] = true;for(int i = h[u];~i;i = ne[i]){int j = e[i];if(!dfn[j]){tarjan(j);low[u] = min(low[u],low[j]);}else if(in_st[j])low[u] = min(low[u],dfn[j]);}map<string,int> M;if(dfn[u] == low[u]){++scc_cnt;int y;do{y = Q.top();Q.pop();in_st[y] = false;id[y] = scc_cnt;Size[scc_cnt]++;M[str[y]]++;ans = max(ans,M[str[y]]);}while(y != u);}
}void init(){idx = ti = 0;scc_cnt = 0;ans = 0;memset(dfn,0,sizeof dfn);memset(low,0,sizeof low);memset(Size,0,sizeof Size);memset(h,-1,sizeof h);memset(in_st,false,sizeof in_st);
}int getmin(string str)
{int len=str.length();int i=0,j=1,k=0;while(i<len&&j<len&&k<len){int t=str[(i+k)%len]-str[(j+k)%len];if(!t) k++;else{if(t>0) i=i+k+1;else j=j+k+1;if(i==j) j++;k=0;}}return min(i,j);
}int main(){while(~scanf("%d%d",&n,&m)){init();for(int i = 1;i <= n;i++){string p;cin >> p;str[i] = p;int t = getmin(str[i]);int back = t;int j;for(j = 0;back < p.length();j++,back++) str[i][j] = p[back];for(int k = 0;k < t;j++,k++) str[i][j] = p[k];}while(m--){int a,b;scanf("%d%d",&a,&b);add(a,b);}for(int i = 1;i <= n;i++)if(!dfn[i])tarjan(i);printf("%d\n",ans);}return 0;
}