题解 P2812 【校园网络【[USACO]Network of Schools加强版】】

何大佰 · 2019-08-23 17:17:20 · 题解

这题其实是水题

本题秘诀：有向图求强联通分量缩点建新图判断入度

问题1即求强连通分量.

问题2则求新图入度为0的个数，因为入度为0的是无法到达的.

#include<bits/stdc++.h>
using namespace std;
const int N=30050;//随性开大点就OK 
int n,low[N],pre[N],deep,scc,belong[N],in[N],ans1,ans2;//deep为访问顺序，in为入度，scc为缩点后个数 
bool isv[N];//判断是否在栈中 
stack<int>sta;
vector<int>link[N<<1];//缩点前 
vector<int>link1[N<<1];//缩点后 
void dfs(int u)//常规dfs求强连通（块）分量 
{
  pre[u]=low[u]=++deep;
  sta.push(u);
  isv[u]=1;
  for(int i=0;i<link[u].size();i++)
  {
    int v=link[u][i];
    if(!pre[v])
    {
      dfs(v);
      low[u]=min(low[u],low[v]);
    }
    else if(isv[v])
      low[u]=min(low[u],pre[v]);
  }
  if(pre[u]==low[u])
  {
    scc++;
    int v;
    do
    {
      v=sta.top();sta.pop();
      belong[v]=scc;
    }while(v!=u);//注意，u要出栈，若写成while则u无法出栈 
  }
}
int main()
{
  ios::sync_with_stdio(0);
  cin>>n;
  int y;
  for(int i=1;i<=n;i++)//输入 
  {
    while(cin>>y)
    {
      if(y==0)
        break;
      link[i].push_back(y);     
    }
  }
  for(int i=1;i<=n;i++)//求强联通分量，即为ans1 
    if(!pre[i])
    {
      dfs(i);
      ans1++;
    }
  for(int i=1;i<=n;i++)//建立新图 
    for(int k=0;k<link[i].size();k++)
    {
      int j=link[i][k];
      if(belong[i]!=belong[j])
        in[belong[j]]++;
    }
  for(int i=1;i<=scc;i++)
    if(in[i]==0)//入度为0的无法到达，需加边 
      ans2++;
  cout<<ans1<<endl<<ans2<<endl;
  return 0;
}