NC15707. 可达性
描述
输入描述
第一行为两个整数 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
C++(clang++ 11.0.1) 解法, 执行用时: 200ms, 内存消耗: 9712K, 提交时间: 2023-07-27 19:57:01
#include<bits/stdc++.h>
using namespace std;
int in[100050];
vector<int>g[100050],ans;
int p[100050];
void dfs(int u,int fa)
{
if(fa==p[u]) return;
p[u]=fa;
for(int i=0;i<g[u].size();i++)
{
dfs(g[u][i],fa);
}
}
int main()
{
int n,m;
cin>>n>>m;
while(m--)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
in[v]++;
}
for(int i=1;i<=n;i++)
{
if(in[i]==0)
dfs(i,i);
}
for(int i=1;i<=n;i++)
{
if(p[i]==0)
dfs(i,i);
}
for(int i=1;i<=n;i++)
if(p[i]==i)
ans.push_back(i);
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++)
{
//if(i) cout<<" ";
cout<<ans[i]<<" ";
}
}