P3436 [POI2006]PRO-Professor Szu

· · 题解

P3436 [POI2006]PRO-Professor Szu

首先，容易发现若一个大小大于 1 的 SCC 或自环（下称为不合法结构）能够到达教学楼，则该不合法结构内部每个点到教学楼的路径数量都是无穷大。因此 SCC 缩点 + 建反图 拓扑排序，不合法结构不能入队。拓扑排序同时记录路径数 f_i 表示从 i 到 n+1 的路径数量。因为不能取模，所以要对 36501 取 \min。

但题目没有保证每个点都能到教学楼（题面有误），所以需要先将反图上入度为 0 的非教学楼点入队跑一遍拓扑排序。注意此时不合法结构可以入队，因为它们没有到达教学楼的路径。

最后，若出现没有入队的点，说明这个点能够到达一个不合法结构，因此路径数同样为无穷大。此外，若 f_i>36500 也不符合题意。时间复杂度线性。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m, ed, ban[N], deg[N], f[N];
int dn, dfn[N], low[N], cn, col[N], top, stc[N], vis[N];
struct linklist {
  int cnt, hd[N], nxt[N], to[N];
  void add(int u, int v) {nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v;}
} e, g;
void tarjan(int id) {
  dfn[id] = low[id] = ++dn, stc[++top] = id, vis[id] = 1; // 0 -> 1
  for(int _ = e.hd[id]; _; _ = e.nxt[_]) {
    int it = e.to[_];
    if(!dfn[it]) tarjan(it), low[id] = min(low[id], low[it]);
    else if(vis[it]) low[id] = min(low[id], dfn[it]);
  }
  if(low[id] == dfn[id]) {
    col[id] = ++cn, ban[cn] = stc[top] != id;
    while(stc[top] != id) col[stc[top]] = cn, vis[stc[top--]] = 0; // id -> cn
    vis[id] = 0, top--;
  }
}
int main() {
#ifdef ALEX_WEI
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
#endif
  cin >> n >> m;
  for(int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    e.add(u, v);
  }
  for(int i = 1; i <= n + 1; i++) if(!dfn[i]) tarjan(i);
  for(int i = 1; i <= n + 1; i++)
    for(int _ = e.hd[i]; _; _ = e.nxt[_]) {
      int it = e.to[_];
      if(i == it) ban[col[i]] = 1;
      else if(col[i] != col[it]) g.add(col[it], col[i]), deg[col[i]]++;
    }
  ed = col[n + 1];
  queue<int> q;
  for(int i = 1; i <= cn; i++) if(i != ed && !deg[i]) q.push(i);
  memset(vis, 0, sizeof(vis));
  while(!q.empty()) {
    int t = q.front();
    q.pop(), vis[t] = 1;
    for(int _ = g.hd[t]; _; _ = g.nxt[_]) {
      int it = g.to[_];
      if(!--deg[it] && it != ed) q.push(it);
    }
  }
  if(!ban[ed]) assert(!deg[ed]), q.push(ed), f[ed] = 1;
  while(!q.empty()) {
    int t = q.front();
    q.pop(), vis[t] = 1;
    for(int _ = g.hd[t]; _; _ = g.nxt[_]) {
      int it = g.to[_];
      if(ban[it]) continue;
      f[it] = min(36501, f[it] + f[t]);
      if(!--deg[it]) q.push(it);
    }
  }
  vector<int> ans;
  for(int i = 1; i <= n; i++)
    if(!vis[col[i]] || f[col[i]] == 36501)
      ans.push_back(i);
  if(!ans.empty()) puts("zawsze");
  else {
    int mx = 0;
    for(int i = 1; i <= n; i++) {
      if(f[col[i]] > mx) mx = f[col[i]], ans.clear();
      if(f[col[i]] == mx) ans.push_back(i);
    }
    cout << mx << "\n";
  }
  cout << ans.size() << "\n";
  for(int it : ans) cout << it << " ";
  return cerr << "Time: " << clock() << endl, 0;
}
/*
2022/5/25
start coding at 8:35
finish debugging at 9:11
*/