SP6818 CAPCITY - Capital City 题解

FFTotoro · 2023-08-03 17:14:40 · 题解

因为图中有环，考虑缩点。

缩点之后考虑什么样的点可以成为首都。显然最多一个 SCC 内会产生首都——假设我们对缩完点的所有 SCC 进行一次拓扑排序，一定是仅有一个出度为 0 的 SCC 里面的点都可以成为首都——所有的点都能到达它（当然也有可能存在多个出度为 0 的，但这样显然无解）。

这样只用统计出度并判断出度为 0 的点是否唯一即可。代码实现十分简单，是个裸的 tarjan 算法模板。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int main(){
  ios::sync_with_stdio(false);
  int n,m,o=0,r=-1; cin>>n>>m;
  vector<pii> e(m);
  vector<vector<int> > g(n);
  for(auto &[u,v]:e)
    cin>>u>>v,g[--u].emplace_back(--v);
  //  SPOJ 的评测机是 C++14 的，写代码时可相应替换
  vector<int> d(n),l(n),c(n,-1);
  stack<int> s;
  function<void(int)> tarjan=[&](int u){
    d[u]=l[u]=++o,s.emplace(u);
    for(int i:g[u])
      if(!d[i])tarjan(i),l[u]=min(l[u],l[i]);
      else if(c[i]<0)l[u]=min(l[u],d[i]);
    if(d[u]==l[u]){
      r++; while(s.top()!=u)
        c[s.top()]=r,s.pop();
      c[u]=r,s.pop();
    }
  };
  for(int i=0;i<n;i++)
    if(!d[i])tarjan(i); // tarjan 模板
  map<pii,bool> p;
  d.resize(r+1),fill(d.begin(),d.end(),0);
  for(auto [u,v]:e)
    if(c[u]!=c[v]&&!p[make_pair(c[u],c[v])])
      p[make_pair(c[u],c[v])]=true,d[c[u]]++;
  bool f=true;
  for(int i=0;i<=r;i++)
    if(!d[i]){
      if(f)f=false; // 第一次
      else cout<<"0\n",exit(0); // 第二次，不唯一，无解
    }
  for(int i=0;i<=r;i++)
    if(!d[i]){
      vector<int> w;
      for(int j=0;j<n;j++)
        if(c[j]==i)w.emplace_back(j);
      cout<<w.size()<<endl;
      for(int i:w)cout<<i+1<<' ';
      cout<<endl; break;
    } // 找出那个特定的 SCC
  return 0;
}