2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=5100; vector<int>G[N]; int tsp,cnt,scc[N],low[N],dfn[N]; stack<int>stk;bool instk[N]; void tarjan(int x) { low[x]=dfn[x]=++tsp; stk.push(x);instk[x]=true; for(int y:G[x]) { if(dfn[y]==0) { tarjan(y); low[x]=min(low[x],low[y]); } else if(instk[y]==true)low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]) { cnt++; for(int z=-1;z!=x;) { z=stk.top();stk.pop();instk[z]=false; scc[z]=cnt; } } } int main() { int n,m; while(scanf("%d", &n)!=EOF&&n) { scanf("%d", &m); memset(G,0,sizeof(G)); for(int i=1,x,y;i<=m;i++) { scanf("%d%d", &x, &y); G[x].push_back(y); } tsp=cnt=0;memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn)); memset(scc,0,sizeof(scc));memset(instk,0,sizeof(instk)); for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i); vector<int>cd(cnt+1); for(int i=1;i<=n;i++)for(int j:G[i])if(scc[i]!=scc[j])cd[scc[i]]++; for(int i=1;i<=n;i++)if(cd[scc[i]]==0)printf("%d ", i); printf("\n"); } return 0; } -
0
#include<bits/stdc++.h> using namespace std; const int N=5100; vector<int>G[N]; int tsp,cnt,scc[N],low[N],dfn[N]; stack<int>stk;bool instk[N]; void tarjan(int x) { low[x]=dfn[x]=++tsp; stk.push(x);instk[x]=True; for(int y:G[x]) { if(dfn[y]==0) { tarjan(y); low[x]=min(low[x],low[y]); } else if(instk[y]==True)low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]) { cnt++; for(int z=-1;z!=x;) { z=stk.top();stk.pop();instk[z]=False; scc[z]=cnt; } } } int main() { int n,m; while(scanf("%d",&n)!=EOF&&n) { scanf("%d",&m); memset(G,0,sizeof(G)); for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),G[x].push_back(y); tsp=cnt=0;memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn)); memset(scc,0,sizeof(scc));memset(instk,0,sizeof(instk)); for(int i=1;i<=n;i++)if(dfn[i]==0)tarjan(i); vector<int>cd(cnt+1);//所在连通分支没有出度的点为sink点 for(int i=1;i<=n;i++)for(int j:G[i])if(scc[i]!=scc[j])cd[scc[i]]++; for(int i=1;i<=n;i++)if(cd[scc[i]]==0)printf("%d ",i); printf("\n"); } return 0; }
- 1
信息
- ID
- 347
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 247
- 已通过
- 58
- 上传者