团结就是力量

Link: https://ac.nowcoder.com/acm/problem/14411

Description

点击查看题面

从小老师就教育我们，一根筷子容易折断，而一捆筷子不容易折断。
因为要出战世界杯，我们需要考虑派一只队伍出战，而我们希望出战的队伍的团结力最大。
而一个队伍的团结力取决于每个人的性格，每个人都有一个性格基因【（由字符串表示），比如小明的性格基因为：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

输出描述:

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

示例1
输入
5 5
abbcde
bbcdea
cdeabb
efg
fge
1 2
2 3
3 4
4 5
5 1
6 7
abbcde
bbcdea
cdeabb
efg
fge
gef
1 2
2 3
3 1
4 5
5 6
6 4
2 4
输出
3
3
说明
第一个样例题干中有所描述。这里1想和2出战，2想和3出战，3想和4出战，4想和5出战，5又想和1出战，那么就相当于每个人都想要互相一起出战，所以这就是一个队伍。
第二个样例中，123号三个人是一个队伍，456号是一个队伍，虽然2想和4一起出战，但是已知m条信息中，不能构成4想和2出战的信息出来，所以六个人不能变成一个队伍。

Probelm solving

这道题的意思就是给你一些人，告诉你单向选择的结果，并且a选b，b选c，等于a选c。每个人都有一个字符串，可以以循环的方式随意变换。每组成员的团结力就是字符串相等的个数（任意变换后）。当且仅当两个人互相选了才可以成组。

首先解决分组的问题，直接用tarjan缩点就可以了。
然后就是团结力的问题了，我们可以给每个字符串设定一个规则，将每个字符串以里面字典序最小的元素做开头，作为变换的终点。然后统计相同组相同字符串的个数即可。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define mem(name,val) memset(name,val,sizeof(name));
const int maxn = 1e5+10;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
int d[4][2]={1,0,0,1,-1,0,0,-1},n,m;
string s[maxn];
vector<int> g[maxn];
vector<string> final[maxn];
int dfn[maxn],color[maxn],low[maxn],cnt,top,sta[maxn],vis[maxn],scc;
void init()
{
    for(int i=0;i<=n;i++)   g[i].clear(),final[i].clear();
    mem(dfn,0);mem(low,0);mem(sta,0);mem(vis,0);mem(color,0);
    top=scc=0;
    cnt=1;
}
void dfs(int u){
    vis[u]=1;
    low[u]=dfn[u]=cnt++;
    sta[++top]=u;
    for(auto v:g[u]){
        if(vis[v]==0)   dfs(v);
        if(vis[v]==1)   low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u]){
        scc++;
        do{
            low[sta[top]]=scc;
            color[sta[top]]=scc;
            vis[sta[top]]=-1;
        }
        while(sta[top--]!=u);
    }
}
int main() {
    ios::sync_with_stdio(0);
    #ifdef Uncle_drew
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #else
    #endif
    while(cin>>n>>m){
        init();
        for(int i=1;i<=n;i++){
            string ss;
            cin>>ss;
            int l=ss.size(),pos=0;char begin=ss[0];
            for(int j=1;j<l;j++){
                if(ss[j]<=begin){
                    pos=j;
                    begin=ss[j];
                }
            }
            string mid="";
            for(int j=pos,tot=0;tot<l;j++,tot++){
                mid+=ss[j%l];
            }
            ss=mid;
            s[i]=mid;
        }
        for(int i=1,x,y;i<=m;i++){
            cin>>x>>y;
            g[x].pb(y);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i]){
                dfs(i);
            }
        }
        for(int i=1;i<=n;i++){
            final[color[i]].pb(s[i]);
        }
        int ans=0;
        for(int i=1;i<=scc;i++){
            map<string,int> ma; 
            for(auto j:final[i]){
                ma[j]++;
            }
            for(auto ohuo:ma){
                ans=max(ans,ohuo.second);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
赏