关于本题子图计数的疑惑
查看原帖
关于本题子图计数的疑惑
545986
Jerrycyx楼主2024/7/25 20:34

代码如下:

//%%% stO Ronz Orz %%%
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

int quick_read()
{
	int x=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
	return x*w;
}

const int N=1e5+5,M=1e6+5;
int n,m,modX;
int ansK,ansC;
pair<int,int> save[M];

struct Allan{
	int to,nxt;
}raw_edge[M],scc_edge[M];
int raw_idx,raw_head[N];
inline void raw_add(int x,int y)
{
	raw_edge[++raw_idx]={y,raw_head[x]};
	raw_head[x]=raw_idx;
	return;
}
int scc_idx,scc_head[N];
inline void scc_add(int x,int y)
{
	scc_edge[++scc_idx]={y,scc_head[x]};
	scc_head[x]=scc_idx;
	return;
}

void InputData()
{
	n=quick_read(),m=quick_read(),modX=quick_read();
	for(int i=1;i<=m;i++)
	{
		save[i].first=quick_read(),save[i].second=quick_read();
		raw_add(save[i].first,save[i].second);
	}
	return;
}

int dfn[N],low[N],ti;
int sta[N],statop; bool insta[N];
int scc_belong[N],scc_size[N],scc_tot;
void Tarjan(int x)
{
	low[x]=dfn[x]=++ti;
	sta[++statop]=x,insta[x]=true;
	for(int i=raw_head[x];i;i=raw_edge[i].nxt)
	{
		int y=raw_edge[i].to;
		if(!dfn[y])
		{
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(insta[y])
			low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x])
	{
		int tmp=0;
		scc_tot++;
		do
		{
			tmp=sta[statop];
			insta[tmp]=false,sta[statop--]=0;
			scc_belong[tmp]=scc_tot;
			scc_size[scc_tot]++;
		}while(tmp!=x);
	}
	return;
}

int scc_endeg[N];
void RebuildTree()
{
	for(int i=1;i<=m;i++)
	{
		save[i].first=scc_belong[save[i].first];
		save[i].second=scc_belong[save[i].second];
	}
	sort(save+1,save+m+1);
	for(int i=1;i<=m;i++)
	{
		if(save[i].first==save[i].second) continue;
		if(save[i].first!=save[i-1].first||save[i].second!=save[i-1].second)
		{
			scc_add(save[i].first,save[i].second);
			scc_endeg[save[i].second]++;
		}
	}
	return;
}

int maxlen[N],lencnt[N];
queue<int> top_q;
void TopSort()
{
	for(int i=1;i<=scc_tot;i++)
		if(!scc_endeg[i])
		{
			top_q.push(i);
			maxlen[i]=scc_size[i];
			lencnt[i]=1%modX;
		}
	while(!top_q.empty())
	{
		int x=top_q.front(); top_q.pop();
		for(int i=scc_head[x];i;i=scc_edge[i].nxt)
		{
			int y=scc_edge[i].to;
			if(maxlen[x]+scc_size[y]>maxlen[y])
			{
				maxlen[y]=maxlen[x]+scc_size[y];
				ansK=max(ansK,maxlen[y]);
				lencnt[y]=lencnt[x];//这里
			}
			if(maxlen[x]+scc_size[y]==maxlen[y])
				lencnt[y]=(lencnt[y]+lencnt[x])%modX;
			scc_endeg[y]--;
			if(!scc_endeg[y]) top_q.push(y);
		}
	}
	return;
}

void MainSolve()
{
	for(int i=1;i<=n;i++)
		if(!dfn[i]) Tarjan(i);
	RebuildTree();
	TopSort();
	return;
}

void OutputAns()
{
	for(int i=1;i<=scc_tot;i++)
		if(maxlen[i]==ansK) ansC=(ansC+lencnt[i])%modX;
	printf("%d\n%d\n",ansK,ansC);
	return;
}

int main()
{
	InputData();
	MainSolve();
	OutputAns();
	return 0;
}

在第 124124 行中,lencnt[y]=lencnt[x]; 是错误的,而 lencnt[y]=0; 则正确,但是当更新到一个更大的链时,链的数量不应该更新成源链的数量吗?

并且在题解中写的也是 ans[edges[i].to]=ans[t] 而不是 00,我很不理解。

2024/7/25 20:34
加载中...