题意:求在图上可以被所有点到达的点的数量。
首先通过tarjan缩点,将所有内部两两可达的子图缩为一点,新图即为一个有向无环图(即DAG)。
在这个DAG上,若存在不止一个所有点均可到达的点,则所有点不满足题目要求。若存在一个,则该点所代表的连通分量的点数即为答案。
//DAG(有向无环图)上面至少存在一个出度为0的点,否则必然可以成环。
#include#include #include #include using namespace std;typedef long long LL;const int N=10007;int n,m;vector adj[N];int time_tag;int dfn[N]; // dfs序int low[N]; // low[u]表示u及其后代所能追溯到的最早的祖先点v的dfn[v]值 int sccno[N];int scc_cnt; int size[N]; //size[i]表示编号为i的连通分量的大小int d[N]; //d[i]==0时表示,编号为i的连通分量不认为任何其他分量popular stack st;void init(){ time_tag=scc_cnt=0; memset(sccno,0,sizeof(sccno)); memset(dfn,0,sizeof(dfn)); for(int i=1;i<=n;i++) adj[i].clear(); memset(d,0,sizeof(d));}void dfs(int u){ dfn[u]=low[u]=++time_tag; st.push(u); for(int i=0;i