思路
首先tarjan缩点,保证是一个DAG之后,再输出topo排序的起点就可以了。
不过数据是不是放水了,我求出来的强连通分量是按访问顺序定谁是fa的,交上去也是对的。难道不应该是要保证每个scc的fa都是里面编号最小那个点吗?所以我弄了个flag数组意义注释了。莫名其妙就A了希望大佬能帮我解答一下。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
inline void read(int &data){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=f*-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
data=x*f;
}
struct E{
int next,from,to;
}e[maxn<<1];
int n,m,u,v;
int head[maxn],cnt,ru[maxn];
int stk[maxn],top;
int dfn[maxn],low[maxn],idx;
int sz[maxn],bel[maxn],vis[maxn],sccnum;
//int flag[maxn];//表示SCC中编号最小的点
vector<int>ans;
vector<int>G[maxn];
void addedge(int from,int to){
e[++cnt].next=head[from];
e[cnt].from=from;
e[cnt].to=to;
head[from]=cnt;
}
void tarjan(int x,int pre){
dfn[x]=low[x]=++idx;
stk[++top]=x;
vis[x]=1;
for(int i=head[x];i;i=e[i].next){
int to=e[i].to;
if(to==pre) continue;
if(!dfn[to]){
tarjan(to,x);
low[x]=min(low[x],low[to]);
}else if(vis[to]) low[x]=min(low[x],dfn[to]);
}
if(dfn[x]==low[x]){
int y;sccnum++;
while(y=stk[top--]){
bel[y]=x;
//flag[x]=min(y,x);
vis[y]=0;
if(x==y) break;
}
}
}
signed main(){
read(n);read(m);
for(int i=1;i<=n;i++) bel[i]=i;//,flag[i]=i;
for(int i=1;i<=m;i++){
read(u);read(v);
addedge(u,v);
}
//tarjan求强连通分量
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i,0);
}
}
if(sccnum==1){
cout<<1<<endl;
return 0;
}
for(int i=1;i<=n;i++){
for(int j=head[i];j;j=e[j].next){
int to=e[j].to;
if(bel[i]!=bel[to]) ru[bel[to]]++;//ru[flag[bel[to]]]++;
}
}
//拓扑排序并输出出发点
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
//if(flag[bel[i]]==i&&!ru[i]){ //没访问过并且入度为0
if(bel[i]==i&&!ru[i]){
ans.push_back(i);
}
}
//sort(ans.begin(),ans.end());
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
return 0;
} 
京公网安备 11010502036488号