USACO Section 5.3 Network of Schools - 回顾Tarjan求强连通分量

网友投稿 320 2022-08-25

USACO Section 5.3 Network of Schools - 回顾Tarjan求强连通分量

这道题一看我就感觉做过..但不记得是怎么做的了...第一感是并查集...找出一类一类有公共祖先的点...公共祖先个数则为第一问的解...第二问就是要始各个公共祖先能形成一个圈..并且每个树的叶子要能到达祖先...就写了一个Floyd+DFS的东东...结果过了前面4个数据...WA了...仔细一想...不对啊..这道题用并查集是错误的...

再一研究...发现这道题其实就是个求强连通分量..果然..找到了去年10月自己的这个解题报告..POJ1236..和这道题一模一样..

​

好吧...好久没写Tarjan了...又熟悉复习了一遍..

Program：

/* ID: zzyzzy12 LANG: C++ TASK: schlnet*/ #include #include #include #include #include #include#include#include #include #define oo 2000000005 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std; struct node{ int x,y,next; }line[10005];int n,m,_link[105],DFS[105],LOW[105],TYPE[105],num;int TYPENUM,ans1,ans2; bool InTheStack[105];stack mystack;void Tarjan(int x){ int k; mystack.push(x); LOW[x]=DFS[x]=++num; InTheStack[x]=true; k=_link[x]; while (k) { if (!DFS[line[k].y]) { Tarjan(line[k].y); LOW[x]=min(LOW[x],LOW[line[k].y]); }else if (InTheStack[line[k].y]) { LOW[x]=min(LOW[x],DFS[line[k].y]); } k=line[k].next; } if (LOW[x]==DFS[x]) { TYPENUM++; do { k=mystack.top(); mystack.pop(); TYPE[k]=TYPENUM; InTheStack[k]=false; }while (LOW[k]!=DFS[k]); } return;}int main() { freopen("schlnet.in","r",stdin); freopen("schlnet.out","w",stdout); scanf("%d",&n); int x,y,k,p; bool IN[105],OUT[105]; m=0; memset(_link,0,sizeof(_link)); for (x=1;x<=n;x++) { while (~scanf("%d",&y)) { if (!y) break; m++; line[m].x=x; line[m].y=y; line[m].next=_link[x]; _link[x]=m; } } memset(DFS,0,sizeof(DFS)); num=0; TYPENUM=0; for (x=1;x<=n;x++) if (!DFS[x]) { memset(InTheStack,false,sizeof(InTheStack)); while (!mystack.empty()) mystack.pop(); Tarjan(x); } memset(IN,false,sizeof(IN)); memset(OUT,false,sizeof(OUT)); p=0; for (k=1;k<=m;k++) if (TYPE[line[k].x]!=TYPE[line[k].y]) { OUT[TYPE[line[k].x]]=true; IN[TYPE[line[k].y]]=true; } ans1=ans2=0; for (k=1;k<=TYPENUM;k++) { if (!IN[k]) ans1++; if (!OUT[k]) ans2++; } if (ans1>ans2) ans2=ans1; if (!ans1) ans1=1; if (TYPENUM==1) ans2=0; printf("%d\n%d\n",ans1,ans2); return 0; }

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

标签：数据
上一篇:2022年如何进行抖音营销呢？（抖音2020年销售额）
下一篇:USACO Section 5.4 Canada Tour - DP..
相关文章

 发表评论

暂时没有评论，来抢沙发吧~