POJ 2553-题意很重要...

POJ 2553-题意很重要...

看是题目看错了...以为和上一个找大牛的一样...样例正好也符合..结果WA了N次...中间也有犯的一些小错误...总是不细心...

题意是说求这些点:自己能到达的点一定能到达自己...抽象来看..就是求出各个强连通分量...这些强连通分量中没有出度的..里面所有点是解..

这个处理比找大牛那题简单些...没必要缩点构图了...做完Tarjan后扫描次所有边...用sum[ ] 来统计各个强连通分量的出度...最后扫一遍所有点..其所在的强连通分量的sum为0则输出这个点...这样即又保证了从大到小的输出...

Program:

#include#include#include#define MAXN 5001using namespace std;struct pp{ int x,y,next; }line[MAXN*5];int n,m,link[MAXN],i,p,low[MAXN],dfn[MAXN],tp[MAXN],numtp,sum[MAXN];bool instack[MAXN],used[MAXN];stack mystack;void tarjan(int h){ int k; instack[h]=true; mystack.push(h); low[h]=dfn[h]=++p; k=link[h]; while (k) { if (!dfn[line[k].y]) { tarjan(line[k].y); low[h]=min(low[h],low[line[k].y]); }else if (instack[line[k].y]) { low[h]=min(low[h],dfn[line[k].y]); } k=line[k].next; } k=h; if (low[k]==dfn[k]) { numtp++; do { k=mystack-(); tp[k]=numtp; mystack.pop(); instack[k]=false; }while ( low[k]!=dfn[k]); } return; } void getanswer(){ int i; memset(instack,false,sizeof(instack)); while (!mystack.empty()) mystack.pop(); memset(tp,0,sizeof(tp)); memset(dfn,0,sizeof(dfn)); p=0; numtp=0; for (i=1;i<=n;i++) if (!dfn[i]) tarjan(i); for (i=1;i<=n;i++) if (!tp[i]) { printf("\n"); return; } memset(link,0,sizeof(link)); memset(sum,0,sizeof(sum)); for (i=1;i<=m;i++) if (tp[line[i].x]!=tp[line[i].y]) { p++; sum[tp[line[i].x]]++; } for (i=1;i<=n;i++) if (!sum[tp[i]]) printf("%d ",i); printf("\n"); return;}int main(){ while (~scanf("%d%",&n)) { if (!n) break; scanf("%d",&m); memset(link,0,sizeof(link)); memset(line,0,sizeof(line)); for (i=1;i<=m;i++) { scanf("%d%d",&line[i].x,&line[i].y); line[i].next=link[line[i].x]; link[line[i].x]=i; } getanswer(); } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。