团结就是力量

C++14(g++5.4) 解法, 执行用时: 828ms, 内存消耗: 133672K, 提交时间: 2020-05-14 16:55:24

//
// Created by ZHY on 2020/5/12.
//
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=19260817;
const int MX=2001000;

ll n,m,cnt,sum;
int ans=0;
vector<int>ve[MX];
int dfn[MX],low[MX];
bool vis[MX];
stack<int>st;
string s[MX];
map<string,int>mp;

void tarjan(int x){
    dfn[x]=low[x]=++cnt;
    st.push(x);vis[x]=1;
    for(int i:ve[x]){
        if(!dfn[i]){
            tarjan(i);
            low[x]=min(low[i],low[x]);
        }else if(vis[i]){
            low[x]=min(dfn[i],low[x]);
        }
    }
    if(low[x]==dfn[x] ){
        int xx,k;sum++;
        mp.clear();
        do{
            k=st.top();st.pop();
            xx=++mp[s[k]];
            vis[k]=0;
            ans=max(xx,ans);
        }while(k!=x);
    }

}

int main()
{
    while(cin>>n>>m) {
        for (int i = 1; i <= n; i++)
        {
            ve[i].clear();vis[i]=0;
            dfn[i]=low[i]=0;
        }
        while(!st.empty()){
            st.pop();
        }
        ans=0;
        for(int i=1;i<=n;i++)
        {
            cin>>s[i];
            sort(s[i].begin(),s[i].end());
        }
        for(int i=0,x,y;i<m;i++)
        {
            cin>>x>>y;
            ve[x].push_back(y);
        }
        for(int i=1;i<=n;i++)
        {
            if(!dfn[i]){
                tarjan(i);
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 377ms, 内存消耗: 20312K, 提交时间: 2023-05-10 18:47:48

#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;
	}
}

C++ 解法, 执行用时: 331ms, 内存消耗: 10716K, 提交时间: 2022-01-11 15:44:09

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int h[N],e[N],ne[N],idx;
int dfn[N],low[N],timestamp;
int stk[N],top,ans;
string s[N];
char ss[N];
bool in_stk[N];
map<string,int>mp;

void init()
{
	memset(h,-1,sizeof h);
	idx=timestamp=ans=0;
	memset(dfn,0,sizeof dfn);
	memset(low,0,sizeof low);
}

void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}

void tarjan(int u)
{
	dfn[u]=low[u]=++timestamp;
	stk[top++]=u,in_stk[u]=1;
	for(int i=h[u]; ~i; i=ne[i])
	{
		int v=e[i];
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(in_stk[v])
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u])
	{
		int y;
		do
		{
			y=stk[--top];
			in_stk[y]=0;
			mp[s[y]]++;
			ans=max(ans,mp[s[y]]);
		}
		while(y!=u);
		mp.clear();
	}
}

int main()
{

	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		init();
		for(int i=1; i<=n; i++)
		{
			scanf("%s",ss+1);
			int len=strlen(ss+1);
			sort(ss+1,ss+len+1);
			s[i]=(ss+1);
		}
		for(int i=1; i<=m; i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			add(x,y);
		}
		for(int i=1; i<=n; i++)
		{
			if(!dfn[i])tarjan(i);
		}
		printf("%d\n",ans);
	}
}

详情