[POI2006]PRO-Professor Szu

拓扑排序 图论

题面

有$n$个别墅以及一个主建筑楼，有$m$条无向边，从每个别墅都有很多种不同方式走到主建筑楼。
其中不同的定义是：每条边可以走多次，如果走边的顺序有一条不同即称两方式不同。
询问经过边数最多的不同方式是多少，以及有多少个别墅有这么多方式，按照顺序输出别墅编号。

• $n,m\leq10^6$

解析

显然如果一栋别墅在环内（包括自环），第一个答案就是无限。
所以在统计完答案无限的别墅后，必须缩点，才能统计其他别墅的答案。
此时判断答案无限的标准：

• 有无自环
• 联通块大小大于$1$

接下来设$f[i]$为走到$i$点的方式数。
则边界为$f[n+1]=1$
那么转移方程式为$f[u]=\sum_{v\in 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\n",ans);
  printf("%d\n",top);
  fp(i,1,top) printf("%d ",sta[i]);puts("");
  return 0;
}