割点和图（割边）

割点： 在连通的无向图中，删除一个点和与它所相连的边，无向图不再连通，说明这个点是割点。
思路: 从一个点开始深搜，当这个点不经过他的父亲节点不能返回到比这个父节点更早的时间戳，说明这个点的父节点是割点。
low[v]>=dfn[u]
注意： 判断割点时分两种情况，如果父节点是根节点的话，至少两个儿子才能形成割点！
割边就是去掉一条边使这个图不连通。
low[v]>dfn[u]；不能经过u->v这条边，所以不能等于low[u] (可以用三角形举例)

/*POJ - 1144 求割点数目*/
#include
#include
#include
using namespace std;
vector<int>edge[110];
int cnt;
int dfn[110],low[110],root,flag[111];
/*考虑图不连通？*/
void Tarjan(int u,int fa)
{int child=0;dfn[u]=low[u]=++cnt;for(int i=0; i<edge[u].size(); i++){child++;/*!!! 统计儿子数量*/int v=edge[u][i];if(!dfn[v])/*深搜*/{Tarjan(v,u);low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]&&u!=root)/*!!!大于等于*/{flag[u]=1;/*儿子回到的最早时间戳大于等于x,x不是根节点*/}else if(u==root&&child>=2){/*根节点，至少两个儿子*/flag[u]=1;}}else if(u!=v)/*!!! v点走过*/{low[u]=min(low[u],dfn[v]);}}return ;
}
int main()
{int n;while(~scanf("%d",&n)&&n){int m,t;char c;root=1;cnt=0;for(int i=0; i<=n; i++){edge[i].clear();dfn[i]=0;low[i]=0;flag[i]=0;}while(~scanf("%d",&m)&&m){while(1){scanf("%c",&c);if(c=='\n')break;scanf("%d",&t);edge[m].push_back(t);edge[t].push_back(m);// printf("%d <---> %d\n",t,m);}}Tarjan(1,1);int sum=0;for(int i=1; i<=n; i++)if(flag[i])sum++;printf("%d\n",sum);}return 0;
}

/*割边*/
#include
using namespace std;
#define N 1000
int n,m,first[N],nex[N],w=1,dfn[N],low[N],flag[N],u[N],v[N],root,index;
void Tarjan(int x,int father)
{int child=0;index++;/*计算时间戳*/dfn[x]=low[x]=index;for(int i=first[x];i!=-1;i=nex[i]){int y=v[i];/* x->y */if(!dfn[y])/*没有被访问过*/{Tarjan(y,x);low[x]=min(low[x],low[y]);if(low[y]>dfn[x])/*这条边是不是割边*/printf("%d %d\n",x,y);}else if(x!=father)/*不通过父节点访问*/low[x]=min(low[y],dfn[x]);/*在割点中不一样low的值不对*/}return;
}
int main()
{index=0;int y,x;scanf("%d%d",&n,&m);memset(flag,0,sizeof(flag));memset(first,-1,sizeof(first));for(int i=0;i<m;i++){scanf("%d%d",&x,&y);/*无向图*/u[w]=x,v[w]=y;nex[w]=first[x];first[x]=w;w++;u[w]=y,v[w]=x;nex[w]=first[y];first[y]=w;w++;}root=1;/*根节点*/Tarjan(1,1);printf("割点为：\n");for(int i=0;i<=n;i++)if(flag[i])printf("%d\n",i);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！