时间限制：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的点
最后输出时要排序
代码：
代码有详细的注释
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
struct node
{
int v, next;
}edge[maxn];
vector<int>p;
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].v=to;
edge[cnt].next=head[from];
head[from]=cnt;
}
void tarjan(int u) {
dfn[u]=low[u]= ++tot;
vis[u]=1;
s.push(u);
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[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 {
v=s.top();
s.pop();
color[v]=block;
pre[block]=min(v, pre[block]);//pre保存的是同强连通分量中编号最小点
vis[v]=0;
} while (v!=u);
}
}
int main()
{
cin>>n>>m;
memset(head,-1,sizeof(head));
memset(pre,INF,sizeof(pre));
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
if(block==1){
cout <<"1"<< endl;
return 0;
}
for(int i=1;i<=n;i++){
for(int j=head[i];j!=-1;j=edge[j].next){
int u=color[i];
int v=color[edge[j].v];//判断u和v是不是在同一个强连通分量
if(u!=v)in[v]++;//如果不是u指向v，v就记录入度
}
}
for(int i=1;i<=block;i++){
//此处已经进行完压缩，压缩后还有block个点
if(!in[i]) //如果一个点没有入度
p.push_back(pre[i]);
}
sort(p.begin(),p.end());
cout<<p.size()<<endl;
for(int i=0;i<p.size();i++) cout<<p[i]<< " ";
cout<<endl;
return 0;
}
京公网安备 11010502036488号