制作网页网站的软件,做电影资源网站有哪些,出租网站空间,下载一个百度导航题目传送门 这个题其实就是tarjan缩点的板子题对吧....至少我是这么想的 首先这是个有向图#xff0c;对于一个有向图#xff0c;我们肯定要考虑环的存在与否#xff0c;恰好这个题又是让我们找出最少的点#xff0c;使得这几个点能够走遍全图 那么#xff0c;显然#x…题目传送门 这个题其实就是tarjan缩点的板子题对吧....至少我是这么想的 首先这是个有向图对于一个有向图我们肯定要考虑环的存在与否恰好这个题又是让我们找出最少的点使得这几个点能够走遍全图 那么显然对于每一个强连通分量我们看做一个点即可因为强连通分量中每两个点之间一定能从一个点到另一个点即从一个点出发一定能够走遍整个强连通分量 缩完点之后我们得到一个DAG显然对于每一个入度为零的点我们都需要发布消息其余入度不为零的点都可以通过这些入度为零的点走到 于是这题就A了 #include iostream
#include cstdlib
#include cstdiousing namespace std;const int N1e55;
const int M5e55;struct edge{int to,next;
}e[M];int n,m,dfn[N],low[N],cnt,head[N];
int idx[N],s[N],top,tot,sum;
bool ins[N];int ind[N],ans;inline void build(int u,int v){e[tot].nexthead[u];head[u]tot;e[tot].tov;return ;
}inline void tarjan(int cur){s[top]cur;ins[cur]true;dfn[cur]low[cur]cnt;for(int ihead[cur];i;ie[i].next){int ke[i].to;if(!dfn[k]){tarjan(k);low[cur]min(low[cur],low[k]);}else if(ins[k]) low[cur]min(low[cur],dfn[k]);}if(low[cur]dfn[cur]){sum;while(s[top1]!cur){idx[s[top]]sum;ins[s[top--]]false;}}return ;
}int main(){scanf(%d%d,n,m);for(int i1;im;i){register int u,v;scanf(%d%d,u,v);build(u,v);}for(int i1;in;i) if(!dfn[i]) tarjan(i);for(int i1;in;i)for(int jhead[i];j;je[j].next){int ke[j].to;if(idx[i]!idx[k]) ind[idx[k]];}for(int i1;isum;i) if(!ind[i]) ans;printf(%d\n,ans);return 0;
} 转载于:https://www.cnblogs.com/Equinox-Flower/p/9648558.html
