思路
首先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; }