武陟网站建设,广州市天河区,化妆品网站建设方案,做外贸主页网站用什么的空间好点来源#xff1a;牛客网 文章目录题目描述题解#xff1a;代码#xff1a;时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K
64bit IO Format: %lld题目描述 给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边…来源牛客网 文章目录题目描述题解代码时间限制C/C 1秒其他语言2秒
空间限制C/C 262144K其他语言524288K
64bit IO Format: %lld题目描述 给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图 输出一个尽可能小的点集使得从这些点出发能够到达任意一点如果有多个这样的集合输出这些集合升序排序后字典序最小的。 输入描述: 第一行为两个整数 1 ≤ n, m ≤ 105 接下来 M 行每行两个整数 1 ≤ u, v ≤ 105 表示从点 u 至点 v 有一条有向边。 数据保证没有重边、自环。 输出描述: 第一行输出一个整数 z表示作为答案的点集的大小 第二行输出 z 个整数升序排序表示作为答案的点集。 示例1 输入
7 10
4 5
5 1
2 5
6 5
7 2
4 2
1 2
5 3
3 5
3 6输出
2
4 7题解
很显然用tarjan来做 我们先进行缩点 因为边是有向边我们可以记录搜点后每个点的入度与出度情况其实光记录入度就可以 我们要找从这些点出发可以找到其他点那我们是不是必须带上那些没有入度的点因为这些点连入度都没有其他点根本不可能指向它只能是我们主动从这些点出发。 如果一个点有入点那么我们无需找他找他的上家也就是指向它的点即可这样向上找最后得到的也是入度为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);}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];//判断u和v是不是在同一个强连通分量if(u!v)in[v];//如果不是u指向vv就记录入度 }}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;
}
