它能分割图为cut,直接tarjan求点双联通分量就好

作者: 编程  发布:2019-08-30

POJ 1523 SPF (割顶 点双连通分量)

题意就是求出在一个图上去除一个点之后,那个图会变成多少个子连通图。

显然我们要求出割顶。我的代码套用了刘汝佳的大白书的tarjan算法,用一个数组cnt[]记录一个点是多少个点双连通分量的割顶。当发现一个点是割顶的时候,就cnt[i] 。最后,如果一个点是一棵dfs树的树根时,就输出cnt[i],否则就输出cnt[i] 1(因为那个点有父亲,而cnt数组记录的相当于是该点的儿子个数)。

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
struct Edge
{
 int u,v;
 Edge(int uu,int vv)
 {
  u=uu;v=vv;
 }
 Edge(){}
};
const int maxn=1005;
int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt;
vectorG[maxn],bcc[maxn];
vector > ans;
int cnt[maxn];
bool isfa[maxn];
stacks;

int dfs(int u,int fa)
{
 int lowu=pre[u]=  dfs_clock;
 int child=0;
 for(int i=0;i=pre[u])
   {
    iscut[u]=true;cnt[u]  ;
    bcc_cnt  ;bcc[bcc_cnt].clear();
    for(;;)
    {
     Edge x=s.top();s.pop();
     if(bccno[x.u]!=bcc_cnt){bcc[bcc_cnt].push_back(x.u);bccno[x.u]=bcc_cnt;}
     if(bccno[x.v]!=bcc_cnt){bcc[bcc_cnt].push_back(x.v);bccno[x.v]=bcc_cnt;}
     if(x.u==u&&x.v==v) break;
    }
   }
  }
  else if(pre[v]maxed) maxed=u;
    scanf("%d",&v);
    if(v>maxed) maxed=v;
    valid=true;
    u--,v--;
    G[u].push_back(v);
    G[v].push_back(u);
   }
   else {flag=false;break;}
  }
  if(!flag) break;
  if(valid==false) break;
  find_bcc(maxed);
  bool hascut=false;
  for(int i=0;i<maxed;i  ) {="" if(iscut[i])="" hascut="true;" if(!isfa[i])ans.push_back(make_pair(i 1,cnt[i] 1));="" else="" ans.push_back(make_pair(i 1,cnt[i]));="" }="" cas  ;="" printf("network="" #%dn",cas);="" if(!hascut)="" printf("="" no="" spf="" nodesn");="" for(int="" i="0;i 

1523 SPF (割顶 点双连通分量) 题意就是求出在一个图上去除一个点之后,那个图会变成多少个子连通图。 显然我们要求出割顶。我的代...

一、基本概念:

这里先给出结论:
  对于非根节点的割点,它能分割图为cut[i] 1个连通分量;对于根节点割点,它能分割图为cut[i]个连通分量
  至于为什么,找了好久没找到答案...
F - SPF
题意:
求删点割点后,割点所割连通分量数

题意:求出所有的割顶,而且还有输出该割顶连接了几个点双连通分量

1.割点:若删掉某点后,原连通图分裂为多个子图,则称该点为割点

#include <cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<set>
#include<algorithm>
#include<iterator>
using namespace std;
const int MAXN=1010;
const int MAXE=200010;
struct Node
{
    int to,next;
}edge[MAXE];
int head[MAXN],cnt;
void addEdge(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt  ;
}
int cutCnt[MAXN],low[MAXN],dfn[MAXN],clocks;
set<int> cut;
void DFS(int u,int e)
{
    low[u]=dfn[u]=  clocks;
    int child=0;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        if(i==(e^1)) continue;
        int v=edge[i].to;
        if(dfn[v]==0)
        {
            child  ;
            DFS(v,i);
            low[u]=min(low[v],low[u]);
            if(low[v]>=dfn[u])
            {
                cut.insert(u);
                cutCnt[u]  ;
            }
        }
        else if(dfn[v]<dfn[u])
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(e<0&&child==1)
    {
        set<int>::iterator it=cut.find(u);
        if(it!=cut.end()) cut.erase(it);
    }
    else if(e!=-1) cutCnt[u]  ;//非根节点
}
void work(int n)
{
    memset(dfn,0,sizeof(dfn));
    memset(cutCnt,0,sizeof(cutCnt));
    clocks=0;
    cut.clear();
    for(int i=1;i<=n;i  )
    {
        if(dfn[i]==0)
        {
            DFS(i,-1);
        }
    }
}
int main()
{
    int n,m,a,b,cas=1,maxv;
    while(true)
    {
        maxv=0;
        scanf("%d",&a);
        maxv=max(maxv,a);
        if(a==0) break;
        scanf("%d",&b);
        maxv=max(maxv,b);
        memset(head,-1,sizeof(head));
        cnt=0;
        addEdge(a,b);
        addEdge(b,a);
        while(true)
        {
            scanf("%d",&a);
            maxv=max(maxv,a);
            if(a==0) break;
            scanf("%d",&b);
            maxv=max(maxv,b);
            addEdge(a,b);
            addEdge(b,a);
        }
        work(maxv);
        printf("Network #%dn",cas  );
        if(cut.size()==0) printf("  No SPF nodesn");
        else
        {
            for(set<int>::iterator it=cut.begin();it!=cut.end();it  )
            {
                printf("  SPF node %d leaves %d subnetsn",*it,cutCnt[*it]);
            }
        }
        printf("n");
    }
}

题解:直接tarjan求点双联通分量就好了,可以在加入边的时候记录加入次数,大于1的都是桥,输入输出很恶心,注意格式

2.割点集合:在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个连通块,就称这个点集为割点集合

其实一开始不知道有上面那个结论,所以我最初的做法是先求出所有的割点和点连通分量,然后再对每个割点求从该割点出发的每条边的另一个端点的不同的点连通分量数。

9159.com 19159.com 2

3.点连通度:最小割点集合中的顶点数。

#include <cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<set>
#include<algorithm>
#include<iterator>
using namespace std;
const int MAXN=1010;
const int MAXE=200010;
struct Node
{
    int to,next;
}edge[MAXE];
int head[MAXN],cnt;
void addEdge(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt  ;
}
struct Edge
{
    int u,v;
    Edge(){}
    Edge(int u,int v):u(u),v(v){}
};
int cutCnt[MAXN],low[MAXN],dfn[MAXN],clocks,bccno[MAXN],bcc_cnt;
int vis[MAXN];
stack<Edge> sta;
set<int> cut;
void DFS(int u,int e)
{
    low[u]=dfn[u]=  clocks;
    int child=0;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        if(i==(e^1)) continue;
        int v=edge[i].to;
        Edge ee(u,v);
        if(dfn[v]==0)
        {
            sta.push(ee);
            child  ;
            DFS(v,i);
            low[u]=min(low[v],low[u]);
            if(low[v]>=dfn[u])
            {
                cut.insert(u);
                bcc_cnt  ;
                while(true)
                {
                    Edge x=sta.top();
                    sta.pop();
                    if(bccno[x.u]!=bcc_cnt) {bccno[x.u]=bcc_cnt;}
                    if(bccno[x.v]!=bcc_cnt) {bccno[x.v]=bcc_cnt;}
                    if(x.u==u&&x.v==v) break;
                }
            }
        }
        else if(dfn[v]<dfn[u])
        {
            sta.push(ee);
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(e<0&&child==1)
    {
        set<int>::iterator it=cut.find(u);
        if(it!=cut.end()) cut.erase(it);
    }
}
void work(int n)
{
    memset(dfn,0,sizeof(dfn));
    clocks=bcc_cnt=0;
    memset(bccno,0,sizeof(bccno));
    while(!sta.empty()) sta.pop();
    cut.clear();
    for(int i=1;i<=n;i  )
    {
        if(dfn[i]==0)
        {
            DFS(i,-1);
        }
    }
    int sum;
    for(set<int>::iterator it=cut.begin();it!=cut.end();it  )
    {
        int u=*it;
        sum=0;
        memset(vis,0,sizeof(vis));
        for(int j=head[u];j!=-1;j=edge[j].next)
        {
            int v=edge[j].to;
            if(vis[bccno[v]]==0)
            {
                vis[bccno[v]]=1;
                sum  ;
            }
        }
        cutCnt[u]=sum;
    }
}
int main()
{
    int n,m,a,b,cas=1,maxv;
    while(true)
    {
        maxv=0;
        scanf("%d",&a);
        maxv=max(maxv,a);
        if(a==0) break;
        scanf("%d",&b);
        maxv=max(maxv,b);
        memset(head,-1,sizeof(head));
        cnt=0;
        addEdge(a,b);
        addEdge(b,a);
        while(true)
        {
            scanf("%d",&a);
            maxv=max(maxv,a);
            if(a==0) break;
            scanf("%d",&b);
            maxv=max(maxv,b);
            addEdge(a,b);
            addEdge(b,a);
        }
        work(maxv);
        printf("Network #%dn",cas  );
        if(cut.size()==0) printf("  No SPF nodesn");
        else
        {
            for(set<int>::iterator it=cut.begin();it!=cut.end();it  )
            {
                printf("  SPF node %d leaves %d subnetsn",*it,cutCnt[*it]);
            }
        }
        printf("n");
    }
}
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m 1,r,rt<<1|1

using namespace std;
using namespace __gnu_cxx;

const double g=10.0,eps=1e-7;
const int N=1000 10,maxn=100000 10,inf=0x3f3f3f;

map<int,int>ma[N];
vector<int>v[N],bcc[N];
int dfn[N],low[N];
int index,num;
int bccno[N],iscut[N];
struct edge{int from,to;};
stack<edge>s;
void tarjan(int u,int f)
{
    low[u]=dfn[u]=  index;
    for(int i=0;i<v[u].size();i  )
    {
        int x=v[u][i];
        edge e=(edge){u,x};
        if(x==f)continue;
        if(!dfn[x])
        {
            s.push(e);
            tarjan(x,u);
            low[u]=min(low[u],low[x]);
            if(low[x]>=dfn[u])
            {
                num  ;bcc[num].clear();
                for(;;)
                {
                    edge p=s.top();s.pop();
                    if(bccno[p.from]!=num)
                    {
                        bccno[p.from]=num;
                        bcc[num].pb(p.from);
                        iscut[p.from]  ;
                    }
                    if(bccno[p.to]!=num)
                    {
                        bccno[p.to]=num;
                        bcc[num].pb(p.to);
                        iscut[p.to]  ;
                    }
                    if(p.from==e.from&&p.to==e.to)break;
                }
            }
        }
        else
        {
            if(dfn[x]<dfn[u])low[u]=min(low[u],dfn[x]);
        }
    }
}
void init()
{
    memset(dfn,0,sizeof dfn);
    memset(low,0,sizeof low);
    memset(bccno,0,sizeof bccno);
    memset(iscut,0,sizeof iscut);
    index=num=0;
    for(int i=1;i<=1000;i  )
    {
        v[i].clear();
        bcc[i].clear();
        ma[i].clear();
    }
    while(!s.empty())s.pop();
}
int main()
{
    int a,b,n=0,cnt=0;
    while(~scanf("%d",&a))
    {
        if(a==0)break;
        init();
        scanf("%d",&b);
        n=max(n,max(a,b));
        v[a].pb(b);
        v[b].pb(a);
        ma[a][b]=ma[b][a]=1;
        while(~scanf("%d",&a))
        {
            if(a==0)break;
            scanf("%d",&b);
            n=max(n,max(a,b));
            if(!ma[a][b])
            {
                v[a].pb(b);
                v[b].pb(a);
                ma[a][b]=ma[b][a]=1;
            }
        }
        for(int i=1;i<=n;i  )
            if(!dfn[i])
                tarjan(i,-1);
      /*  cout<<num<<endl;
        for(int i=1;i<=num;i  )
        {
            for(int j=0;j<bcc[i].size();j  )
                cout<<bcc[i][j]<<" ";
            cout<<endl;
        }*/
        printf("Network #%dn",  cnt);
        bool ok=0;
        for(int i=1;i<=n;i  )
        {
            if(iscut[i]>1)
            {
                ok=1;
                printf("  SPF node %d leaves %d subnetsn",i,iscut[i]);
            }
        }
        if(!ok)printf("  No SPF nodesn");
puts("");
    }
    return 0;
}
/************

************/

4.割边(桥):删掉它之后,图必然会分裂为两个或两个以上的子图。

View Code

5.割边集合:如果有一个边集合,删除这个边集合以后,原图变成多个连通块,就称这个点集为割边集合

 

6.边连通度:一个图的边连通度的定义为,最小割边集合中的边数。

7.缩点:把没有割边的连通子图缩为一个点,此时满足任意两点之间都有两条路径可达。

注:求块<>求缩点。缩点后变成一棵k个点k-1条割边连接成的树。而割点可以存在于多个块中。

8.双连通分量:分为点双连通和边双连通。它的标准定义为:点连通度大于1的图称为点双连通图,边连通度大于1的图称为边双连通图。通俗地讲,满足任意两点之间,能通过两条或两条以上没有任何重复边的路到达的图称为双连通图。无向图G的极大双连通子图称为双连通分量

 

二、Tarjan算法的应用论述:

1.求强连通分量(见)、割点、桥、缩点:

对于Tarjan算法中,我们得到了dfn和low两个数组,

low[u]:=min(low[u],dfn[v])——(u,v)为后向边,v不是u的子树;

low[9159.com,u]:=min(low[u],low[v])——(u,v)为树枝边,v为u的子树;

下边对其进行讨论:

(1)若low[v]>=dfn[u],则u为割点,节点v的子孙和节点u形成一个块。因为这说明v的子孙不能够通过其他边到达u的祖先,这样去掉u之后,图必然分裂为两个子图。这样我们处理点u时,首先递归u的子节点v,然后从v回溯至u后,如果发现上述不等式成立,则找到了一个割点u,并且u和v的子树构成一个块。

//v[x]:x是割点时割成的连通分量数
void tarjan(int x)
{
    v[x]=1,dfn[x]=low[x]=  num;
    for(int i=head[x];i;i=next[i])
    if(!v[ver[i]])
    {
        tarjan(ver[i]);
        low[x]=min(low[x],low[ver[i]]);
        if(dfn[x]<=low[ver[i]]) 
            v[x]  ;
    }
    else 
        low[x]=min(low[x],dfn[ver[i]]);
    if((x==1&&v[x]>2)||(x>1&&v[x]>1)) 
        v[x]=2; 
    else 
        v[x]=1;  //v[x]=2表示该点为割点,注意其中第一个点要特判
}

 

(2)若low[v]>dfn[u],则(u,v)为割边。但是实际处理时我们并不这样判断,因为有的图上可能有重边,这样不好处理。我们记录每条边的标号(一条无向边拆成的两条有向边标号相同),记录每个点的父亲到它的边的标号,如果边(u,v)是v的父亲边,就不能用dfn[u]更新low[v]。这样如果遍历完v的所有子节点后,发现low[v]=dfn[v],说明u的父亲边(u,v)为割边。

void tarjan(int x)
{
    vis[x]=1;
    dfn[x]=low[x]=  num;
    for(int i=head[x];i;i=next[i])
    if(!vis[ver[i]])
    {
        p[ver[i]]=edge[i];//记录父亲边
        tarjan(ver[i]);
        low[x]=min(low[x],low[ver[i]]);
    }
    else if(p[x]!=edge[i])//不是父亲边才更新
        low[x]=min(low[x],dfn[ver[i]]);
    if(p[x]&&low[x]==dfn[x]) 
        f[p[x]]=1;//是割边
}

 

2.求双连通分量以及构造双连通分量:

对于点双连通分支,实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈,存储当前双连通分支,在搜索图时,每找到一条树枝边或后向边(非横叉边),就把这条边加入栈中。如果遇到某时满足DFS(u)<=Low(v),说明u是一个割点,同时把边从栈顶一个个取出,直到遇到了边(u,v),取出的这些边与其关联的点,组成一个点双连通分支。割点可以属于多个点双连通分支,其余点和每条边只属于且属于一个点双连通分支。

对于边双连通分支,求法更为简单。只需在求出所有的桥以后,把桥边删除,原图变成了多个连通块,则每个连通块就是一个边双连通分支。桥不属于任何一个边双连通分支,其余的边和每个顶点都属于且只属于一个边双连通分支。

一个有桥的连通图,如何把它通过加边变成边双连通图?方法为首先求出所有的桥,然后删除这些桥边,剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点,再把桥边加回来,最后的这个图一定是一棵树,边连通度为1。

统计出树中度为1的节点的个数,即为叶节点的个数,记为leaf。则至少在树上添加(leaf 1)/2条边,就能使树达到边二连通,所以至少添加的边数就是(leaf 1)/2。具体方法为,首先把两个最近公共祖先最远的两个叶节点之间连接一条边,这样可以把这两个点到祖先的路径上所有点收缩到一起,因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点,这样一对一对找完,恰好是(leaf 1)/2次,把所有点收缩到了一起。

 

3.求最近公共祖先(LCA)

在遍历到u时,先tarjan遍历完u的子树,则u和u的子树中的节点的最近公共祖先就是u,并且u和【u的兄弟节点及其子树】的最近公共祖先就是u的父亲。注意到由于我们是按照DFS顺序遍历的,我们可用一个color数组标记,正在访问的染色为1,未访问的标记为0,已经访问到即在【u的子树中的】及【u的已访问的兄弟节点及其子树中的】染色标记为2,这样我们可以通过并查集的不断合并更新,通过getfather实现以上目标。

void tarjan(int x)
{
    fa[x]=x,color[x]=1;
    int i,y;
    for(i=head[x];i;i=next[i])
    if(color[y=ver[i]]==0)
    {
        tarjan(y);
        fa[y]=x;
    }
    for(i=headquery[x];i;i=nextquery[i])
    if(color[y=query[i]]==2) 
        ans[i]=get(y);
    color[x]=2;
}

 

参考例题:POJ 1523、2942、3694、3352、3177  Tyvj P1111 

转自:BYVoid,稍作修改99999999

本文由9159.com发布于编程,转载请注明出处:它能分割图为cut,直接tarjan求点双联通分量就好

关键词: 9159.com