a tutorial on computer science

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  21 随笔 :: 0 文章 :: 17 评论 :: 0 Trackbacks
一种很简洁的写法,那个用栈存的算法实在是比较难看。
问题大概是这样子的:
无向图割点:比较特殊,因为可能子节点从别的路返回到父亲点,如果父亲点再从自己返回到更高的父亲点。。所以
low[father] = 
minst{
   dfn[father],
   low[child],
   dfn[others]
};

无向图割边:还可以用上面的公式,对于边u->v,如果low[v] < dfn[u],我们可以认为这是割边

无向图边双联通:
low[father] =
minst{
dfn[father],
low[others],除了返回父亲的边
}
至于为什么会这样,画个图理解下就好

有向图强联通:
和无向图边双联通是一样的,这是不对的!!还没想到好的办法,还得用tarjan算法搞。

无向图点双联通:
用求割点的那个公式,dfs把点放到栈里面,当dfn[u] == low[u]的时候出栈,栈里面的点在一个点双联通里,记得把当前点留在栈里


//无向图边双连通+缩点,已知图是个联通图 

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

const int maxn = 5010;
int nmap[maxn][maxn];

vector<int> edg[maxn];

int dfn[maxn],vis[maxn],low[maxn];

int deg[maxn];

int N,M;

int t;

void dfs(int p,int i)
{
  vis[i] = 1;
  dfn[i] = low[i] = ++t;

  for(int j = 0;j<edg[i].size();j++)
  {
int next = edg[i][j];
if(next == p) continue;
    if(!vis[next])
    {
       dfs(i,next);
    }
    low[i] = min(low[i],low[next]);
  } 
  vis[i] = 2; 
}

int main()
{
  //freopen("in.txt","r",stdin);
  
//freopen("out.txt","w",stdout);
  scanf("%d%d",&N,&M);
  int i,a,b;
  for(i=0;i<M;i++)
  {
    scanf("%d%d",&a,&b);
    if(nmap[a][b]) continue;
    edg[a].push_back(b);
    edg[b].push_back(a);
    nmap[a][b] = 1;
  }
  dfs(1,1);
  int leaf = 0; 
  for(i=1;i<=N;i++)
  {
    for(int j=0;j<edg[i].size();j++)
    {
      if(low[i] != low[edg[i][j]])
        deg[low[i]]++;
    }
  }
  for(i=1;i<=t;i++)
  {
   if(deg[i] == 1) leaf++;
  }
  printf("%d\n",(leaf+1)/2);
  return 0;
}

      
posted on 2012-10-24 22:47 bigrabbit 阅读(509) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理