https://www.zybuluo.com/ysner/note/1251523
题面
有(n)个别墅以及一个主建筑楼，有(m)条无向边，从每个别墅都有很多种不同方式走到主建筑楼。
其中不同的定义是：每条边可以走多次，如果走边的顺序有一条不同即称两方式不同。
询问经过边数最多的不同方式是多少，以及有多少个别墅有这么多方式，按照顺序输出别墅编号。
- (n,mleq10^6)
解析
显然如果一栋别墅在环内（包括自环），第一个答案就是无限。
所以在统计完答案无限的别墅后，必须缩点，才能统计其他别墅的答案。
此时判断答案无限的标准：
- 有无自环
- 联通块大小大于(1)
接下来设(f[i])为走到(i)点的方式数。
则边界为(f[n+1]=1)
那么转移方程式为(f[u]=sum_{vin neighbor} f[v])
显然为了消除后效性需要拓扑排序。
于是从主建筑楼开始拓扑排序即可。
值得注意的是：
- 不能把主建筑楼统计进答案
- 把答案无限的别墅和建筑的(f[i]=inf)，必须等到该点没有入度时再进行。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+7,N=1e6+100,M=36501;
struct Edge{int to,nxt;}e[N<<1],e1[N<<1];
int n,m,h[N],cnt,dfn[N],low[N],sta[N],top,tim,scc,bl[N],in[N],f[N],sz[N],ans;
bool gg[N],vis[N],gu[N];
queue<int>Q;
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il void tarjan(re int u)
{
dfn[u]=low[u]=++tim;vis[u]=1;sta[++top]=u;
re int v;
for(re int i=h[u];i+1;i=e[i].nxt)
{
v=e[i].to;
if(u==v) gg[v]=1;
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
++scc;
do{v=sta[top];bl[v]=scc;sz[scc]++;vis[v]=0;top--;}while(u^v);
}
}
il void Topo()
{
f[bl[n]]=1;if(gu[bl[n]]||sz[bl[n]]>1) f[bl[n]]=M;
fp(i,1,n) if(!in[i]) Q.push(i);
while(!Q.empty())
{
re int u=Q.front();Q.pop();
for(re int i=h[u];i+1;i=e[i].nxt)
{
re int v=e[i].to;--in[v];
f[v]=min(f[v]+f[u],M);
if(!in[v])
{
if((gu[v]||sz[v]>1)&&f[v]) f[v]=M;
Q.push(v);
}
}
}
}
int main()
{
memset(h,-1,sizeof(h));
n=gi()+1;m=gi();
fp(i,1,m)
{
re int u=gi(),v=gi();
add(v,u);
}
fp(i,1,n) if(!dfn[i]) tarjan(i);top=0;
fp(u,1,n)
for(re int i=h[u];i+1;i=e[i].nxt)
{
re int v=e[i].to;
if(bl[u]^bl[v]) e1[++top]=(Edge){bl[u],bl[v]};
}
memset(h,-1,sizeof(h));cnt=0;
fp(i,1,top) add(e1[i].to,e1[i].nxt),++in[e1[i].nxt];
fp(i,1,n) if(gg[i]) gu[bl[i]]=1;
Topo();top=0;
fp(i,1,n-1) ans=max(ans,f[bl[i]]);
fp(i,1,n-1) if(f[bl[i]]==ans) sta[++top]=i;
if(ans==M) puts("zawsze");else printf("%d
",ans);
printf("%d
",top);
fp(i,1,top) printf("%d ",sta[i]);puts("");
return 0;
}