编程开源网站,计算机培训班,app下载网站建设,网站开发及上线过程NC15707 可达性
题目#xff1a;
给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图#xff0c; 输出一个尽可能小的点集#xff0c;使得从这些点出发能够到达任意一点#xff0c;如果有多个这样的集合#xff0c; 输出这些集合升序排序后字典序最小的。
题解:…NC15707 可达性
题目
给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图 输出一个尽可能小的点集使得从这些点出发能够到达任意一点如果有多个这样的集合 输出这些集合升序排序后字典序最小的。
题解:
• 先强连通缩点变成一个有向无环图 • 然后在所有入度为0的点集每一个拿出编号最小的一个点 记录缩点后的入度 for(int i1;in;i){for(int jhead[i];j!-1;jedge[j].next){int ucolor[i];int vcolor[edge[j].v];if(u!v)in[v];//记录入度 }}代码
#includebits/stdc.h
using namespace std;
const int maxn 1e5 5;
const int INF 0x3f3f3f3f;
struct node
{int v, next;
}edge[maxn];
vectorintp;
stack int s;
int dfn[maxn],low[maxn];
int color[maxn],in[maxn];
int tot,block;
int head[maxn],pre[maxn];
int n,m,cnt,C,X;
bool vis[maxn];
void add(int from, int to) {edge[cnt].vto;edge[cnt].nexthead[from];head[from]cnt;
}
void tarjan(int u) {dfn[u]low[u] tot;vis[u]1;s.push(u);for(int ihead[u];i!-1;iedge[i].next) {int vedge[i].v;if (!dfn[v]) {tarjan(v);low[u] min(low[u],low[v]);}else if(vis[v]) low[u]min(low[u],dfn[v]);}if (dfn[u]low[u]) {block;int v;do {vs.top();s.pop();color[v]block;pre[block]min(v, pre[block]);//pre保存的是同强连通分量中编号最小点 vis[v]0;} while (v!u);}
}int main()
{cinnm;memset(head,-1,sizeof(head));memset(pre,INF,sizeof(pre));for(int i0;im;i){int u,v;scanf(%d%d,u,v);add(u,v);}for(int i1;in;i){if(!dfn[i]) tarjan(i);}if(block1){cout 1 endl; return 0; }for(int i1;in;i){for(int jhead[i];j!-1;jedge[j].next){int ucolor[i];int vcolor[edge[j].v];if(u!v)in[v];//记录入度 }}for(int i1;iblock;i){//此处已经进行完压缩压缩后还有block个点 if(!in[i]) //如果一个点没有入度 p.push_back(pre[i]);}sort(p.begin(),p.end());coutp.size()endl;for(int i0;ip.size();i) coutp[i] ;coutendl;return 0;
}NC 19960 [HAOI2006]受欢迎的牛
题目
• 每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛给你M对整数(A,B)表示牛A认为牛B受欢迎。 • 这种关系是具有传递性的如果A认为B受欢迎B认为C受欢迎那么牛A也认为牛C受欢迎。 • 你的任务是求出有多少头牛被所有的牛认为是受欢迎的。
题解
• 强连通缩点 • 唯一的一个出度为0的强连通分量 • 如果有多个出度为0的强连通分量则无解
代码
#includebits/stdc.h
using namespace std;
const int maxn 1e5 5;
const int INF 0x3f3f3f3f;
struct node
{int v, next;
}edge[maxn];
vectorintp;
stack int s;
int dfn[maxn],low[maxn];
int color[maxn],in[maxn];
int tot,block;
int head[maxn],pre[maxn];
int n,m,cnt,C,X;
bool vis[maxn];
void add(int from, int to) {edge[cnt].vto;edge[cnt].nexthead[from];head[from]cnt;
}
void tarjan(int u) {dfn[u]low[u] tot;vis[u]1;s.push(u);for(int ihead[u];i!-1;iedge[i].next) {int vedge[i].v;if (!dfn[v]) {tarjan(v);low[u] min(low[u],low[v]);}else if(vis[v]) low[u]min(low[u],dfn[v]);}if (dfn[u]low[u]) {block;int v;do {vs.top();s.pop();color[v]block;pre[block]min(v, pre[block]);//pre保存的是同强连通分量中编号最小点 vis[v]0;} while (v!u);}
}int main()
{cinnm;memset(head,-1,sizeof(head));memset(pre,INF,sizeof(pre));for(int i0;im;i){int u,v;scanf(%d%d,u,v);add(u,v);}for(int i1;in;i){if(!dfn[i]) tarjan(i);}for(int i1;in;i){for(int jhead[i];j!-1;jedge[j].next){int ucolor[i];int vcolor[edge[j].v];if(u!v)in[u]; }}for(int i1;in;i){//此处已经进行完压缩压缩后还有block个点 if(!in[color[i]]) //如果一个点没有入度 p.push_back(pre[i]);}//sort(p.begin(),p.end());//coutans;coutp.size()endl;//for(int i0;ip.size();i) coutp[i] ;//coutendl;return 0;
}
