题解 | #团结就是力量#

Tarjan 排序

分析:

很显然这题需要使用tarjan求一遍强连通分量,答案就是每个强连通分量的本质相同的字符串的个数的最大值。
首先考虑对字符串的处理,可以选择hash或者是排序。很显然,对于每个本质相同的字符串排序后一定也是相
同的,只需要用一个map存储每个排序后的字符串的个数,在每次求完强连通分量后遍历map更新ans即可

代码:

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1e5+10;
int h[N],ne[N],e[N];
int s[N],top,tot,ans;
int dfn[N];
int scc_cnt,idx;
int low[N];
int ins[N];
map<string,int> mp;
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
string v[N];
void tarjan(int u)
{
	dfn[u]=++tot;
	ins[u]=true;
	low[u]=tot;
	s[++top]=u;
	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(ins[j]) low[u]=min(low[u],dfn[j]); 
	}
	if(low[u]==dfn[u])
	{
		scc_cnt++;
		mp.clear();
		while(1)
		{
			int x=s[top--];
			ins[x]=false;
			mp[v[x]]++;
			if(u==x) break;
		}
		for(auto i:mp) ans=max(ans,i.second);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	while(cin>>n>>m)
	{
		memset(h,-1,sizeof h);
		idx=0,top=0,scc_cnt=0;
		memset(low,0,sizeof low);
		memset(dfn,0,sizeof dfn);
		for(int i=1;i<=n;i++)
		{
			string t;
			cin>>t;
			sort(t.begin(),t.end());
			v[i]=t;
		}
		for(int i=1;i<=m;i++)
		{
			int a,b;
			cin>>a>>b;
			add(a,b);
		}
		ans=0;
		for(int i=1;i<=n;i++) 
		{
			if(!dfn[i])
			{
				tarjan(i);
			}
		}
		cout<<ans<<endl;
	}
}