Network POJ - 1144

Network POJ - 1144

套的啊哈算法上的板子

当初学割点割边板子都是靠背的.. 主要是时间戳这个东西不太理解

就是以某一点为根生成一棵搜索树 意义就是记录每个点的时间戳(感觉也可以理解为树的层数)

越靠后被遍历到 时间戳就越大(层数越高) 看一个父节点的子节点的时间戳是否比父节点要大 如果大 就说明这个子节点除了通过这个父节点以外没有途径回到更小的时间戳(更低的层数) 这样的话 如果去掉这个父节点u 那这子节点以及以这个子节点为根的子树都被割断 u即为割点

#include #include #include using namespace std;struct node{ int v; int next;};node edge[10010];int first[110],book[110],dfn[110],low[110];int n,num,cnt,sum,root;void addedge(int u,int v);void dfs(int cur,int pre);int main(){ int i,u,v; while(scanf("%d",&n)!=EOF) { if(n==0) break; memset(first,-1,sizeof(first)); num=0; while(scanf("%d",&u)!=EOF) { if(u==0) break; while(getchar()!='\n') { scanf("%d",&v); addedge(u,v); addedge(v,u); } } memset(book,0,sizeof(book)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); cnt=0,root=1; dfs(1,-1); sum=0; for(i=1;i<=n;i++) { sum+=book[i]; } printf("%d\n",sum); } return 0;}void addedge(int u,int v){ edge[num].v=v; edge[num].next=first[u]; first[u]=num++; return;}void dfs(int cur,int pre){ int i,v,chd; cnt++,chd=0; dfn[cur]=cnt; low[cur]=cnt; for(i=first[cur];i!=-1;i=edge[i].next) { v=edge[i].v; if(dfn[v]==0) { chd++; dfs(v,cur); if(low[v]=dfn[cur]||cur==root&&chd>=2) { book[cur]=1; } } else if(v!=pre) { if(dfn[v]

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