链接：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;
}
