精华内容
下载资源
问答
  • 1.图的几个概念 (1)连通图:在无向图中,若任意两个顶点vi与vj有路径相通,则称该无向图为连通图 (2)强连通图:在有向图中,若任意两...(4)生成:一个连通图的生成是指一个连通子图,它含有图中全部n个...

    1.图的几个概念

    (1)连通图:在无向图中,若任意两个顶点vi与vj都有路径相通,则称该无向图为连通图
    (2)强连通图:在有向图中,若任意两个顶点vi与vj都有路径相通,则称该有向图为强连通图
    (3)连通网:在连通图中,若图的边具有一定的意义,每一条边都对应着一个数值,称为,权代表着连接两个顶点的代价,称这种连通图叫做连通网
    (4)生成树:一个连通图的生成树是指一个连通子图,它含有图中全部 个顶点,但只有足以构成一棵树的 n-1 条边。一棵有n个顶点的生成树有且仅有n-1条边,如果生成树中再添加一条边,则必定成环
    (5)最小生成树:在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树(Minimum Cost Spanning Tree),简称 MST

    è¿éåå¾çæè¿°

    2.普里姆(Prim)算法的概述

    用于求解图的最小生成树
    贪心策略:每次都选择权值最小的边作为最小生成树的边

    3.普里姆(Prim)算法的基本思路

    (1) 设 G=(V,E)是连通网,T=(U,D)是最小生成树,V,U 是顶点集合,E,D 是边的集合
    (2) 若从顶点 i 开始构造最小生成树,则从集合 V 中取出顶点 i 放入集合 U 中,标记顶点 i 为已被访问,即 visited[i] = true
    (3) 若集合 U 中顶点 ui 与集合 V-U(差集) 中的顶点 vj 之间存在边,则寻找这些边中权值最小的边,但不能构成回路,
    将顶点 vj 加入集合 U 中,将边(ui,vj)加入集合 D 中,标记 visited[vj] = true
    (4) 重复步骤(3),直到 U 与 V 相等,即所有顶点都被标记为访问过,此时 D 中有 n-1 条边,得到最小生成树

    注意在使用普里姆算法(Prim)构造最小生成树的过程中,最小生成树必定不会构成回路,因为顶点 ui 是从已经被访问过的顶点集合 U 中获取到的顶点,顶点 vj 是从未被访问过的顶点集合 V-U(差集) 中获取到的顶点,(ui,vj)构成的边加入到最小生成树中必定不会构成回路,但是使用 克鲁斯卡尔算法(Kruskal) 构造最小生成树时,添加边到最小生成树中,存在构成回路的可能,因此要判断加入的边是否会构成回路,使用 并查集 判断是否会构成回路

    4.普里姆(Prim)算法的代码实现

     

    package com.zzb.algorithm.prim;
    
    import java.io.Serializable;
    import java.util.Arrays;
    
    /**
     * @Auther: Administrator
     * @Date: 2020/3/31 12:56
     * @Description: 普里姆算法:求加权连通图的最小生成树的算法
     * 贪心策略:每次都选择权值最小的边作为最小生成树的边
     */
    public class Prim {
        public static void main(String[] args) {
            // 顶点值数组
            String[] vertexArray = {"A", "B", "C", "D", "E", "F", "G"};
            // 邻接矩阵
            final int N = Integer.MAX_VALUE/2; // 表示不可以连接
            int[][] matrix = new int[vertexArray.length][vertexArray.length];
            matrix[0]=new int[]{N,5,7,N,N,N,2};
            matrix[1]=new int[]{5,N,N,9,N,N,3};
            matrix[2]=new int[]{7,N,N,N,8,N,N};
            matrix[3]=new int[]{N,9,N,N,N,4,N};
            matrix[4]=new int[]{N,N,8,N,N,5,4};
            matrix[5]=new int[]{N,N,N,4,5,N,6};
            matrix[6]=new int[]{2,3,N,N,4,6,N};
            // 创建图对象
            Graph graph = new Graph(vertexArray, matrix);
            // 构造最小生成树
            Graph mst = graph.createMST("G");
            int[][] edgeArray = mst.getEdgeArray();
            // 总权值
            int sum = 0;
            for(int i = 0 ; i < edgeArray.length; i++) {
                for(int j = i+1; j < edgeArray.length; j++) {
                    if(edgeArray[i][j] != Integer.MAX_VALUE/2) {
                        System.out.println("边 <" + mst.getVertexArray()[i] + "," + mst.getVertexArray()[j] + "> " + "权值 " + edgeArray[i][j]);
                        sum += edgeArray[i][j];
                    }
                }
            }
            System.out.println("总权值 == " + sum);
            /*
            边 <A,C> 权值 7
            边 <A,G> 权值 2
            边 <B,G> 权值 3
            边 <D,F> 权值 4
            边 <E,F> 权值 5
            边 <E,G> 权值 4
            总权值 == 25*/
        }
    }
    
    /**
     * 图类
     */
    class Graph implements Serializable {
        private static final long serialVersionUID = 8866902589112221411L;
    
        // 存储图中各个顶点的集合
        private String[] vertexArray;
        // 存储图中各条边的邻接矩阵
        private int[][] edgeArray;
        // 图中某个顶点是否被访问过,初始化为都未被访问
        private boolean[] visited;
    
        /**
         * 构造器初始化
         *
         * @param vertexArray 顶点
         * @param edgeArray 连接矩阵
         */
        public Graph(String[] vertexArray, int[][] edgeArray) {
            this.vertexArray = vertexArray;
            this.edgeArray = edgeArray;
            // 初始化为都未被访问
            this.visited = new boolean[vertexArray.length];
        }
    
        public Graph() {
    
        }
    
        /**
         * 构造最小生成树
         *
         * @param initVertex 从哪个顶点开始构造最小生成树
         * @return 以图的方式保存最小生成树
         */
        public Graph createMST(String initVertex) {
            // 普里姆算法
            Graph mst = prim(this, initVertex);
            return mst;
        }
    
        /**
         * 普里姆算法
         * 贪心策略:每次都选择权值最小的边作为最小生成树的边
         * 
         * @param graph 由哪个图的哪个顶点开始来构造最小生成树
         * @param vertex 由哪个图的哪个顶点开始来构造最小生成树
         * @return 以图的方式保存最小生成树
         */
        private Graph prim(Graph graph, String vertex) {
            // 初始化最小生成树对应的图不连通
            Graph mst = new Graph(); // 最小生成树
            mst.setVertexArray(graph.getVertexArray()); // 顶点
            int[][] edgeArray = new int[graph.getVertexArray().length][graph.getVertexArray().length];
            mst.setEdgeArray(edgeArray); // 边
            for(int i = 0; i < mst.getVertexArray().length; i++) {
                // Integer.MAX_VALUE/2 表示不连通
                Arrays.fill(mst.getEdgeArray()[i], Integer.MAX_VALUE/2);
            }
    
            // 设置顶点 vertex 已被访问
            int indexOfVertex = graph.getIndexOfVertex(vertex);
            graph.getVisited()[indexOfVertex] = true;
    
            // 默认两点之间的最小值(对应图graph中两点之间不连通的值 Integer.MAX_VALUE/2),实时更新
            int min = Integer.MAX_VALUE/2;
            // 被访问过的顶点索引
            int index1 = -1;
            // 未被访问的顶点索引
            int index2 = -1;
            int length = graph.vertexArray.length;
            for(int k = 1; k < length; k++) { // 构成最小生成树所需的循环次数
                // 在每一次构造最小生成树的过程中,已经被访问过的所有顶点中,哪一个顶点 与 未被访问的顶点 距离最短,
                // 然后作为最小生成树的一条边
                for(int i = 0; i < length; i++) { // i 代表顶点集合中已经被访问过的顶点,遍历判断确定是否被访问过
                    for(int j = 0; j < length; j++) { // j 代表顶点集合中未被访问的顶点,遍历判断确定是否未被访问
                        if(graph.getVisited()[i] && !graph.getVisited()[j] && graph.getEdgeArray()[i][j] < min) {
                            min = graph.getEdgeArray()[i][j];
                            index1 = i;
                            index2 = j;
                        }
                    }
                }
                // 设置顶点已被访问
                graph.getVisited()[index2] = true;
                // 构成最小生成树的一条边(因为是无向图)
                mst.getEdgeArray()[index1][index2] = min;
                mst.getEdgeArray()[index2][index1] = min;
                // 重置最小值,进行下一轮最小权值边的选择
                min = Integer.MAX_VALUE/2;
            }
            // 最小生成树
            return mst;
        }
    
        /**
         * 获取各个定点所对应的索引
         *
         * @param vertex 顶点所在集合的值
         * @return 获取各个顶点所对应的索引
         */
        public int getIndexOfVertex(String vertex) {
            for(int i = 0; i < this.vertexArray.length; i++) {
                if(vertex.equals(this.vertexArray[i])) {
                    return i;
                }
            }
            return -1;
        }
    
        public String[] getVertexArray() {
            return vertexArray;
        }
    
        public void setVertexArray(String[] vertexArray) {
            this.vertexArray = vertexArray;
        }
    
        public int[][] getEdgeArray() {
            return edgeArray;
        }
    
        public void setEdgeArray(int[][] edgeArray) {
            this.edgeArray = edgeArray;
        }
    
        public boolean[] getVisited() {
            return visited;
        }
    
        public void setVisited(boolean[] visited) {
            this.visited = visited;
        }
    }
    

     

    展开全文
  • 无向连通图的生成个数

    千次阅读 2015-03-14 09:27:37
    我们知道,每个无向连通图都会有自己的生成。但是大家更熟悉的,是无向图的最小生成(MST)算法。本文旨在讨论计算无向连通图的生成个数的时间复杂度为O(n3)的方法。另外一种时间效率高的递推式方法的讲解在文...

          我们知道,每个无向连通图都会有自己的生成树。但是大家更熟悉的,是无向图的最小生成树(MST)算法。本文旨在讨论计算无向连通图的生成树个数的时间复杂度为O(n3)的方法。另外一种时间效率高的递推式方法的讲解在文末附有链接。

          我们可以利用矩阵在O(n3)的时间内求出无向连通图的生成树个数。对于一个无向连通图,我们可以根据以下规则列出一个矩阵M:

    1. 主对角线上的值M(i,i)为i节点的度。
    2. a[i,j]的值为点i到点j的平行边的条数的相反数。显然,如果i,j不连通,M(i,j)=0。

          通过这样的规则,一个矩阵就在O(n2)的时间内建立起来。

          以图1为例。

          这样,我们就得到了矩阵M:

    参考代码(init):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    begin
      fillchar(ma,sizeof(ma),0);
      readln(n,m);
        for i:=1 to n do
          for j:=1 to n do
             begin
                read(x);
                if x=1 then
                  begin
                     ma[i,i]:=ma[i,i]+1;
                     ma[i,j]:=-1;
                  end;
            end;
    end.

          恩,有了这个矩阵有什么用呢?

    【定理】删除矩阵中任意一个节点的信息,求出剩下的(n-1)*(n-1)矩阵的行列式的值,此值即为这个无向连通图的生成树个数。

     

          定理的证明在这里不再赘述(其实我也不会,知道怎么证明又有什么用呢 可以用数学归纳法证明),如果想知道详细的证明过程,可以参阅文末所附的参考文献,或者在网上查阅。

          经过删除操作,我们得到如下的矩阵M’:

          可是,行列式的值怎么求呢?

          我们知道行列式值的手工求法是经过将行列式降阶,通过如下的定理求得:

    【定理】三阶行列式D= 的值等于它任意一行(列)的所有元素与它们对应的代数余子式乘积之和。

          即:

          用等式表示为:

                    

          当阶数很高,这种方法由于要递归、压栈,不但占用大量内存,而且代码复杂度很高(现在我还没有打出来过 *.*||)。在这里,我们用高斯消元的思想将行列式转化成一个下三角行列式,运用以下性质即可求出行列式的值。 

    【性质】三角形行列式的值等于主对角线上元素的乘积。

          这样,只要我们将行列式进行消元,然后求得主对角线上元素的乘积即可。

    参考代码(make):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    begin
      ans:=1;
      for k:=1 to n do
        begin
          ans:=ans*a[k,k];  //记录对角线乘积
          for i:=k+1 to n do
            if a[i,k]<>0 then
              begin
                zoom:=-a[k,k]/a[i,k];
                ans:=ans/zoom;  //ans也要zoom一下
                for j:=k to n do
                  a[i,j]:=a[k,j]+a[i,j]*zoom;  //消元
              end;
        end;
      writeln(round(ans));
    end;

          下面是一道例题。

    复制代码
    【问题描述】 小夜家教很严……恩,家教很严厉。但俗话说得好“有些鸟是关不住的”。小夜家住一个很大很大
    的湖泊中央的小岛上,湖泊中有还有n个小岛,小岛间有桥相连。任意两个小岛之间都有至少一条路径可
    以到达。小夜很久没有出去玩了,她想到岸上去玩……但是去玩之前她要跟自己的爷爷奶奶叔叔伯伯阿
    姨婶婶大哥大姐小弟小妹打声招呼,所以她要跑遍湖中所有的岛至少一次(当然还有自己家),但是小
    夜有个很邪恶的爸爸,夜爸爸不准小夜出去玩。夜爸爸有足够的人手可以控制住连接岛屿的桥,在从线
    人那打听到小夜的情况后,夜爸爸决定在每一个时刻都增派一票人控制住某一座当前还未被他控制的桥,
    只要小夜路过这些桥就…… 小夜在路上好几次都差点被逮到,她发现这是个问题,于是打开手机向你求助。因为被夜爸爸控制
    的桥会越来越多,她认为走的桥越少越好,所以她想知道当前时刻一共有多少种方案能够让选择n座桥
    并使得任意两个岛屿只有一条路径连通。 【输入格式】 输入文件第一行两个整数n和m,表示湖泊中除了小夜家以外的岛屿数目和夜爸爸会陆续派m票人控
    制桥。 接下来n+1行,每行n+1个整数,其中第i行第j个整数 Aij表示第i号岛屿和第j号岛屿之间是否直
    接有桥相连(0表示不连通,1表示连通)。 再接下来m行,每行两个整数a,b。表示当前时刻他已经控制住第a号岛屿和第b号岛屿直接相连的
    桥。(注:开始时刻夜爸爸没控制一座桥。) 【输出格式】 输出文件共有m+1行,每行一个整数。表示当前时刻的总方案数。 【输入样例】 5 2 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 4 1 1 3 【输出样例】 1296 864 540 【数据范围】 对于40%的数据 0<n<13 对于100%的数据 0<n<26 , 0<m<31 输出数据保证在extended范围内。
    复制代码

    首先注意,解不是n!。原因是路线不一定是链状的,而可能是树状的。这样,问题就转化成求无向连通图的生成树个数的问题了。 

    参考代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    program escape;
      var
        a,ta:array[1..30,1..30]of extended;
        n,m,x,y,i:integer;
        ans:extended;
      procedure init;
        var
          i,j:integer;
        begin
          readln(n,m);
          for i:=1 to n+1 do
            for j:=1 to n+1 do
              begin
                read(x);
                if x=1 then
                  begin
                    a[i,i]:=a[i,i]+1;
                    a[i,j]:=-1;
                  end;
               end;
          ta:=a;
        end;
      procedure make;
        var
          i,j,k:integer;
          zoom:extended;
        begin
          ans:=1;
          for k:=1 to n do
            begin
              ans:=ans*a[k,k];
              for i:=k+1 to n do
                if a[i,k]<>0 then
                  begin
                    zoom:=-a[k,k]/a[i,k];
                    ans:=ans/zoom;
                    for j:=k to n do
                      a[i,j]:=a[k,j]+a[i,j]*zoom;
                  end;
            end;
          writeln(round(ans));
        end;
      begin
        init;
        make;
        for i:=1 to m do
          begin
            readln(x,y);
            ta[x,x]:=ta[x,x]-1;
            ta[y,y]:=ta[y,y]-1;
            ta[x,y]:=0;
            ta[y,x]:=0;
            a:=ta;  //记录原图
            make;
          end;
      end.

       参考链接(均有递推式法

    展开全文
  • 首先理解无环连通图的概念: ①无环连通图一定只有n-1条边 ②图中任意两个点均有可将其连通的边 根据这两点概念就可以写出算法,算法必须满足两点: ①可以统计得到一个图是否连通 ②一个图中边的个数 代码部分: ...

    首先理解无环连通图的概念:
    ①无环连通图一定只有n-1条边
    ②图中任意两个点均有可将其连通的边
    根据这两点概念就可以写出算法,算法必须满足两点:
    ①可以统计得到一个图是否连通
    ②一个图中边的个数
    代码部分:

    int visited[MAXNUM];
    //主算法入口
    bool isTree(Graph& G){
    	for(i=1;i<G.vexnum;i++) visited[i] = false;  //初始化记录已访问顶点的数组
    	int Vnum = 0, Enum = 0;  //用来记录访问到的顶点和边界的数量
    	DFS(G, 1 , Vnum, Enum, visited);
    	if(Vnum == G.vexnum&&Enum == 2(G.vexnum-1)) //最后得到的边数量一定是实际的两倍,因为每条边连着两个顶点
    		return true;//e=2(n-1)即边的数量是顶点数量减一
    	else 
    		return false;
    }
    //主算法,递归深度优先遍历图
    void DFS(Graph& G, int v, int& Vnum, int& Enum, int visited[]){
    	visited[v] = true;  //标记访问到的顶点
    	Vnum++; //访问到的点++
    	int w = FirstNeighbor(G,v); //初始化
    	while(w!=-1){
    		Enum++;  //每访问到一个顶点,就让边的数量++,最后得到的边的数量会是实际数量的两倍
    		if(!visited[w])//如果没有访问过,则进入递归
    			DFS(G, w, Vnum, Enum, visited); //进入递归
    		w= NextNeighbor(G, v, w);
    	}
    }
    	
    
    展开全文
  • 连通图

    千次阅读 2019-05-21 18:56:13
    Network of Schools POJ - 1236 ...题解:先缩点,缩点后得到的求其入度为0、出度为0的结点数in0、out0;答案就是in0和max(in0,out0),特判下只有一个连通分量的情况。 #include<iostream&...

    原题链接:https://cn.vjudge.net/article/371
    ps:为了偷懒,以下建图都是用vector,悄悄和用链式前向星的对比下,(大部分情况下)发现链式前向星用的时间少了一半。

    Network of Schools

    POJ - 1236
    题意:给一个有向图,求最少需要加几个网络到结点,使得这些网络能到达任意一个结点;以及最少需要加入多少个连边,使得图的任意一个点,可达任意其他点。
    题解:先缩点,缩点后得到的树求其入度为0、出度为0的结点数in0、out0;答案就是in0和max(in0,out0),特判下只有一个连通分量的情况。

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<vector>
    #include<stack>
    using namespace std;
    const int maxn=110;
    
    vector<int> ve[maxn];
    int n,cn;
    int dfn[maxn],low[maxn],cnt;
    int in[maxn],out[maxn],color[maxn];
    stack<int> s;
    bool ins[maxn];
    void init()
    {
    	memset(dfn,0,sizeof(dfn));
    	memset(low,0,sizeof(low));
    	memset(ins,0,sizeof(ins));
    	cn=cnt=0;
    	memset(in,0,sizeof(in));
    	memset(out,0,sizeof(out));
    	for(int i=1;i<=n;i++) ve[i].clear();
    	while(!s.empty()) s.pop();
    }
    void tarjan(int u)
    {
    	low[u]=dfn[u]=++cnt;
    	s.push(u);
    	ins[u]=1;
    	for(int i=0;i<ve[u].size();i++){
    		int v=ve[u][i];
    		if(!dfn[v]){
    			tarjan(v);
    			low[u]=min(low[u],low[v]);
    		}else if(ins[v]){//
    			low[u]=min(low[u],dfn[v]);
    		}
    	}
    	if(low[u]==dfn[u]){
    		cn++;
    		while(s.top()!=u){
    			ins[s.top()]=0;
    			color[s.top()]=cn;
    			s.pop();
    		}
    		color[u]=cn;
    		ins[u]=0;s.pop();
    	}
    }
    
    int main()
    {
    	while(~scanf("%d",&n)){
    		int v;
    		init();
    		for(int u=1;u<=n;u++){
    			while(~scanf("%d",&v)){
    				if(!v) break;
    				ve[u].push_back(v);
    			}
    		}
    		
    		for(int i=1;i<=n;i++)
    			if(!dfn[i])
    				tarjan(i);
    			
    		for(int u=1;u<=n;u++){
    			for(int i=0;i<ve[u].size();i++){
    				int v=ve[u][i];
    				if(color[u]!=color[v]){//注意这里 
    					in[color[v]]++;
    					out[color[u]]++;
    				}
    			}
    		}
    		int in0=0,out0=0;
    		for(int i=1;i<=cn;i++){
    			if(!in[i]) in0++;
    			if(!out[i]) out0++; 
    		}
    		if(cn==1){//当只有一个连通分量时,特判 
    			printf("%d\n0\n",in0);
    			continue;
    		}
    		printf("%d\n%d\n",in0,max(in0,out0));
    	}
    	return 0;
    }
    

    Network

    UVA - 315
    题意:给一个无向图(direct line:直达线),求割点数。
    题解:割点:
    1.若为根结点,且子树数大于1
    2.若为非根结点,则父子边u->v满足dfn[u]<=low[v]
    注意的地方:图我用vector储存,对于第1点,不能直接用ve[root].size()来看,因为可能有重边的情况;对于第2点,不能每次遇到dfn[u]<=low[v]就直接ans++,因为u可能重复计数了。

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<vector>
    #include<stack>
    using namespace std;
    const int maxn=110;
    
    vector<int> ve[maxn];
    int n;
    int dfn[maxn],low[maxn],cnt;
    bool vis[maxn];
    int fa[maxn];
    
    void init()
    {
    	memset(dfn,0,sizeof(dfn));
    	memset(low,0,sizeof(low));
    	cnt=0;
    	memset(vis,0,sizeof(vis));
    	for(int i=1;i<=n;i++) ve[i].clear();
    }
    void tarjan(int u,int p)
    {
    	low[u]=dfn[u]=++cnt;
    	fa[u]=p;
    	for(int i=0;i<ve[u].size();i++){
    		int v=ve[u][i];
    		if(!dfn[v]){
    			tarjan(v,u);
    			low[u]=min(low[u],low[v]);
    		}else if(v!=p){
    			low[u]=min(low[u],dfn[v]);
    		}
    	}
    }
    
    int main()
    {
    	while(~scanf("%d",&n)){
    		if(!n) break;
    		int u,v;
    		char ch;
    		init();
    		while(~scanf("%d",&u)){
    			if(!u) break;
    			while(~scanf("%d%c",&v,&ch)){
    				ve[u].push_back(v);
    				ve[v].push_back(u);
    				if(ch=='\n') break;
    			}
    		}
    		for(int i=1;i<=n;i++)
    			if(!dfn[i])
    				tarjan(i,-1);
    		int num=0; 
    		for(int i=2;i<=n;i++){
    			if(fa[i]==1) num++;
    			if(fa[i]!=-1&&fa[i]!=1&&dfn[fa[i]]<=low[i])
    				vis[fa[i]]=1;
    		}
    		int ans=0;
    		if(num>1) ans++;//考虑重边 不能直接用ve[1].size() 
    		//if(ve[1].size()>1) ans++;
    		for(int i=2;i<=n;i++)
    			if(vis[i]) ans++;
    		printf("%d\n",ans);
    	}
    	return 0;
    }
    
    

    Critical Links

    UVA - 796
    给定一个无向图,求割边数,割边的性质:low(v)>dfn(u) 计算时要考虑重边,注意去重。
    sb了,结点从0开始的

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<vector>
    #include<stack>
    using namespace std;
    const int maxn=1010;
    
    vector<int> ve[maxn];
    int n;
    int dfn[maxn],low[maxn],cnt;
    bool vis[maxn];
    int fa[maxn];
    
    struct node{
    	int u,v;
    	bool operator == (const node &b)
    	{
    		return u==b.u&&v==b.v;
    	}
    }cut[maxn*210];
    int tot;
    bool cmp(const node& a,const node& b)
    {
    	if(a.u==b.u) return a.v<b.v;
    	return a.u<b.u; 
    }
    void init()
    {
    	memset(dfn,0,sizeof(dfn));
    	memset(low,0,sizeof(low));
    	cnt=tot=0;
    	memset(vis,0,sizeof(vis));
    	for(int i=0;i<n;i++) ve[i].clear();
    }
    
    void tarjan(int u,int p)
    {
    	low[u]=dfn[u]=++cnt;
    	fa[u]=p;
    	for(int i=0;i<ve[u].size();i++){
    		int v=ve[u][i];
    		if(!dfn[v]){
    			tarjan(v,u);
    			low[u]=min(low[u],low[v]);
    			if(low[v]>dfn[u]){
    				cut[tot].u=u;
    				cut[tot].v=v;
    				if(cut[tot].u>cut[tot].v)
    					swap(cut[tot].u,cut[tot].v);
    				tot++;
    			}
    		}else if(v!=p){
    			low[u]=min(low[u],dfn[v]);
    		}
    		
    	}
    }
    
    int main()
    {
    	while(~scanf("%d",&n)){
    		int u,v,num;
    		init();
    		for(int i=1;i<=n;i++){
    			scanf("%d",&u);
    			scanf(" (%d)",&num);
    			while(num--){
    				scanf("%d",&v);
    				ve[u].push_back(v);
    				ve[v].push_back(u);
    			}
    		}
    		for(int i=0;i<n;i++)
    			if(!dfn[i])
    				tarjan(i,-1);
    		sort(cut,cut+tot,cmp);
    		tot=unique(cut,cut+tot)-cut;
    		
    		printf("%d critical links\n",tot);
    		for(int i=0;i<tot;i++){
    			printf("%d - %d\n",cut[i].u,cut[i].v);
    		}
    		printf("\n");
    	}
    	return 0;
    }
    

    Network

    POJ - 3694
    题意:给一个无向图,q个查询,问加入边后,当前树的割边数。
    题解:先对每个强连通分量缩点,缩点后得到一棵树,如果这树的结点数为ans,那么割边数就是ans-1。对于每次加边操作,我们把这两个点之间的结点都union起来即可,然后根据找当前树的结点数ans,来得到当前割边数ans-1。
    对于缩点,除了用常规的stack方法,还可以用并查集。
    并查集实现:

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<vector>
    #include<cstdio>
    using namespace std;
    const int maxn=100010;
    
    
    int low[maxn],dfn[maxn];
    vector<int> ve[maxn];
    struct node{
    	int u,v;
    }cut[maxn];
    int tot,cnt;
    
    int n,m,q;
    int f[maxn],f2[maxn];
    bool vis[maxn];//dfs
    void init()
    {
    	memset(low,0,sizeof(low));
    	memset(dfn,0,sizeof(dfn));
    	memset(vis,0,sizeof(vis));
    	tot=cnt=0;
    	for(int i=0;i<=n;i++){
    		ve[i].clear();
    		f[i]=f2[i]=i;
    	}
    }
    int find1(int x,int f[])
    {
    	return x==f[x]?x:f[x]=find1(f[x],f);
    }
    void union1(int x,int y,int f[])
    {
    	int fx=find1(x,f),fy=find1(y,f);
    	if(fx!=fy)
    		f[fx]=fy;
    }
    void tarjan(int u,int p)
    {
    	low[u]=dfn[u]=++cnt;
    	for(int i=0;i<ve[u].size();i++){
    		int v=ve[u][i];
    		if(!dfn[v]){
    			tarjan(v,u);
    			low[u]=min(low[u],low[v]);
    			if(low[v]>dfn[u]){
    				cut[tot].u=u;
    				cut[tot].v=v;
    				tot++;
    			}else{
    				union1(u,v,f);
    			}
    		}else if(v!=p){
    			low[u]=min(low[u],dfn[v]);
    		}
    	}
    }
    bool dfs(int u,int v)
    {
    	vis[u]=1;
    	if(u==v) return 1;
    	for(int i=0;i<ve[u].size();i++){
    		int x=ve[u][i];
    		if(vis[x]) continue;
    		if(dfs(x,v)){
    			union1(u,x,f2);
    			return 1;
    		}
    	}
    	return 0;
    }
    int main()
    {
    	int cas=1;
    	while(~scanf("%d%d",&n,&m)){
    		if(!n&&!m) break;
    		init(); 
    		int u,v;
    		for(int i=0;i<m;i++){
    			scanf("%d%d",&u,&v);
    			ve[u].push_back(v);
    			ve[v].push_back(u);
    		}
    		for(int i=1;i<=n;i++)
    			if(!dfn[i]) tarjan(i,0);
    		vector<int> cur;
    		cur.clear();
    		//for(int i=1;i<=n;i++) printf("f[%d]:%d\n",i,f[i]);
    		for(int i=1;i<=n;i++)//把当前树结点存储起来,更新后的树结点都在这里 
    			if(find1(i,f)==i){
    				cur.push_back(i);
    				//printf("root: %d\n",i);
    			}
    		
    		//缩点 建树 
    		for(int i=0;i<=n;i++) ve[i].clear();//clear 
    		for(int i=0;i<tot;i++){
    			u=cut[i].u;
    			v=cut[i].v;
    			u=find1(u,f);//在新树的编号 
    			v=find1(v,f);
    			ve[u].push_back(v);
    			ve[v].push_back(u);
    		}
    		
    		scanf("%d",&q);
    		printf("Case %d:\n",cas++);
    		while(q--){
    			scanf("%d%d",&u,&v);
    			u=find1(u,f);
    			v=find1(v,f);
    			memset(vis,0,sizeof(vis));
    			dfs(u,v);
    			int ans=0;
    			for(int i=0;i<cur.size();i++){
    				v=cur[i];
    				if(v==find1(v,f2)) ans++;
    			}
    			printf("%d\n",ans-1);
    		}
    	}
    	return 0;
    }
    

    stack缩点实现(不知为啥RE 留坑)。

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<vector>
    #include<cstdio>
    #include<stack>
    using namespace std;
    const int maxn=100010;//
    
    
    int low[maxn],dfn[maxn];
    vector<int> ve[maxn];
    struct node{
    	int u,v;
    }cut[maxn];
    int tot,cnt;
    stack<int> s;
    bool ins[maxn];
    int color[maxn],cn;
    int n,m,q;
    int f[maxn];
    bool vis[maxn];//dfs
    void init()
    {
    	memset(low,0,sizeof(low));
    	memset(dfn,0,sizeof(dfn));
    	memset(vis,0,sizeof(vis));
    	memset(ins,0,sizeof(ins));
    	cn=tot=cnt=0;
    	for(int i=0;i<=n;i++){
    		ve[i].clear();
    		f[i]=i;
    	}
    	while(!s.empty()) s.pop();
    }
    int find1(int x)
    {
    	return x==f[x]?x:f[x]=find1(f[x]);
    }
    void union1(int x,int y)
    {
    	int fx=find1(x),fy=find1(y);
    	if(fx!=fy)
    		f[fx]=fy;
    }
    void tarjan(int u,int p)
    {
    	low[u]=dfn[u]=++cnt;
    	s.push(u);
    	ins[u]=1;
    	for(int i=0;i<ve[u].size();i++){
    		int v=ve[u][i];
    		if(!dfn[v]){
    			tarjan(v,u);
    			low[u]=min(low[u],low[v]);
    			if(low[v]>dfn[u]){
    				cut[tot].u=u;
    				cut[tot].v=v;
    				tot++;
    			}//else
    			//	union1(u,v,f);
    			
    		}else if(v!=p){
    			low[u]=min(low[u],dfn[v]);
    		}
    	}
    	if(low[u]==dfn[u]){
    		cn++;
    		while(s.top()!=u){
    			ins[s.top()]=0;
    			color[s.top()]=cn;
    			s.pop();
    		}
    		color[u]=cn;ins[u]=0;
    		s.pop();
    	}
    }
    bool dfs(int u,int v)
    {
    	vis[u]=1;
    	if(u==v) return 1;
    	for(int i=0;i<ve[u].size();i++){
    		int x=ve[u][i];
    		if(vis[x]) continue;
    		if(dfs(x,v)){
    			union1(u,x);
    			return 1;
    		}
    	}
    	return 0;
    }
    int main()
    {
    	int cas=1;
    	while(~scanf("%d%d",&n,&m)){
    		if(!n&&!m) break;
    		init(); 
    		int u,v;
    		for(int i=0;i<m;i++){
    			scanf("%d%d",&u,&v);
    			ve[u].push_back(v);
    			ve[v].push_back(u);
    		}
    		for(int i=1;i<=n;i++)
    			if(!dfn[i]) tarjan(i,0);
    		
    		
    		//缩点 建树 
    		for(int i=0;i<=n;i++) ve[i].clear();//clear 
    		for(int i=0;i<tot;i++){
    			u=cut[i].u;
    			v=cut[i].v;
    			u=color[u];
    			v=color[v];
    			ve[u].push_back(v);
    			ve[v].push_back(u);
    		}
    		
    		scanf("%d",&q);
    		printf("Case %d:\n",cas++);
    		while(q--){
    			scanf("%d%d",&u,&v);
    			u=color[u];
    			v=color[v];
    			memset(vis,0,sizeof(vis));
    			dfs(u,v);
    			int ans=0;
    			for(int i=1;i<=cn;i++){			
    				if(i==find1(i)) ans++;
    			}
    			printf("%d\n",ans-1);
    		}
    	}
    	return 0;
    }
    

    Redundant Paths

    POJ - 3177
    题意:给一个有向图,求最少加入多少边,使得原图的任意两点的路径数有至少2条;即加入边后图的割边数为0,也即加入边后图为双连通图。
    题解:缩点得到一棵树(无向),问题转化为加入多少边,使得树为0割边(双连通)。则加入的边数为 (度数为1的结点数+1)/2。

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<vector>
    #include<cstdio>
    using namespace std;
    const int maxn=5010;
    
    
    int low[maxn],dfn[maxn];
    vector<int> ve[maxn];
    struct node{
    	int u,v;
    }cut[maxn];
    int tot,cnt;
    
    int n,m,q;
    int f[maxn];
    bool vis[maxn];//dfs
    void init()
    {
    	memset(low,0,sizeof(low));
    	memset(dfn,0,sizeof(dfn));
    	memset(vis,0,sizeof(vis));
    	tot=cnt=0;
    	for(int i=0;i<=n;i++){
    		ve[i].clear();
    		f[i]=i;
    	}
    }
    int find1(int x)
    {
    	return x==f[x]?x:f[x]=find1(f[x]);
    }
    void union1(int x,int y)
    {
    	int fx=find1(x),fy=find1(y);
    	if(fx!=fy)
    		f[fx]=fy;
    }
    void tarjan(int u,int p)
    {
    	low[u]=dfn[u]=++cnt;
    	for(int i=0;i<ve[u].size();i++){
    		int v=ve[u][i];
    		if(!dfn[v]){
    			tarjan(v,u);
    			low[u]=min(low[u],low[v]);
    			if(low[v]>dfn[u]){
    				cut[tot].u=u;
    				cut[tot].v=v;
    				tot++;
    			}else{
    				union1(u,v);
    			}
    		}else if(v!=p){
    			low[u]=min(low[u],dfn[v]);
    		}
    	}
    }
    
    int main()
    {
    	while(~scanf("%d%d",&n,&m)){
    		init(); 
    		int u,v;
    		for(int i=0;i<m;i++){
    			scanf("%d%d",&u,&v);
    			ve[u].push_back(v);
    			ve[v].push_back(u);
    		}
    		for(int i=1;i<=n;i++)
    			if(!dfn[i]) tarjan(i,0);
    		//缩点 建树 
    		for(int i=0;i<=n;i++) ve[i].clear();//clear 
    		for(int i=0;i<tot;i++){
    			u=cut[i].u;
    			v=cut[i].v;
    			u=find1(u);//在新树的编号 
    			v=find1(v);
    			ve[u].push_back(v);
    			ve[v].push_back(u);
    		}
    		int ans=0;
    		for(int i=1;i<=n;i++){
    			if(ve[i].size()==1){
    				ans++;
    			}
    		}
    		printf("%d\n",(ans+1)/2);
    	}
    	return 0;
    }
    

    Warm up

    HDU - 4612
    题意:给一个无向图,求加入最少的一条边,使得剩下的割边(桥)最少。
    题解:缩点,缩点后得到的树,对树求直径,则直径就是最多能减少的割边。
    坑点:有重边,这题用vector莫得做了…
    缩点方法,用并查集:

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<vector>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn=200010;
    
    
    int low[maxn],dfn[maxn];
    int tot1,head[maxn];
    struct edge{
    	int v,nxt;
    	bool flag;
    }e[maxn*10];
    struct node{
    	int u,v;
    }cut[maxn*10];
    int tot,cnt;
    
    int n,m,q;
    int f[maxn];
    
    void init()
    {
    	memset(low,0,sizeof(low));
    	memset(dfn,0,sizeof(dfn));
    	memset(vis,0,sizeof(vis));
    	memset(head,-1,sizeof(head));
    	
    	tot1=tot=cnt=0;
    	for(int i=0;i<=n;i++){
    		f[i]=i;
    	}
    }
    void addedge(int u,int v)
    {
    	e[tot1].v=v;e[tot1].nxt=head[u];
    	e[tot1].flag=0;head[u]=tot1++;
    }
    int find1(int x)
    {
    	return x==f[x]?x:f[x]=find1(f[x]);
    }
    void union1(int x,int y)
    {
    	int fx=find1(x),fy=find1(y);
    	if(fx!=fy)
    		f[fx]=fy;
    }
    void tarjan(int u,int p)
    {
    	low[u]=dfn[u]=++cnt;
    	for(int i=head[u];~i;i=e[i].nxt){
    		int v=e[i].v;
    		if(e[i].flag) continue;
    		e[i].flag=e[i^1].flag=1;
    		if(!dfn[v]){
    			tarjan(v,u);
    			low[u]=min(low[u],low[v]);
    			if(low[v]>dfn[u]){
    				cut[tot].u=u;
    				cut[tot].v=v;
    				tot++;
    			}else{
    				union1(u,v);
    			}
    		}else{
    			low[u]=min(low[u],dfn[v]);
    		}
    	}
    }
    int mx;
    int dfs(int u,int fa)
    {
    	int tmp=0;
    	for(int i=head[u];~i;i=e[i].nxt){
    		int v=e[i].v;
    		if(v==fa) continue;
    		int d=dfs(v,u);
    		mx=max(mx,d+tmp);
    		tmp=max(tmp,d);
    	}
    	return tmp+1;
    }
    
    int main()
    {
    	while(~scanf("%d%d",&n,&m)){
    		if(!n&&!m) break;
    		init(); 
    		int u,v;
    		for(int i=0;i<m;i++){
    			scanf("%d%d",&u,&v);
    			addedge(u,v);
    			addedge(v,u);
    		}
    		for(int i=1;i<=n;i++)
    			if(!dfn[i]) tarjan(i,0);
    		//缩点 建树 
    		memset(head,-1,sizeof(head));//clear 
    		tot1=0; 
    		for(int i=0;i<tot;i++){
    			u=cut[i].u;
    			v=cut[i].v;
    			u=find1(u);//在新树的编号 
    			v=find1(v);
    			addedge(u,v);
    			addedge(v,u);
    		}
    		if(!tot){
    			printf("0\n");
    		}else{
    			mx=0;
    			dfs(find1(cut[0].u),-1);
    			printf("%d\n",tot-mx);
    		}
    	}
    	return 0;
    }
    

    用stack缩点,与上一题Poj3694相比,能过。

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<vector>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn=200010;
    
    
    int low[maxn],dfn[maxn];
    int tot1,head[maxn];
    struct edge{
    	int v,nxt;
    	bool flag;
    }e[maxn*10];
    struct node{
    	int u,v;
    }cut[maxn*10];
    int tot,cnt;
    
    int n,m,q;
    int f[maxn];
    
    void init()
    {
    	memset(low,0,sizeof(low));
    	memset(dfn,0,sizeof(dfn));
    	memset(vis,0,sizeof(vis));
    	memset(head,-1,sizeof(head));
    	
    	tot1=tot=cnt=0;
    	for(int i=0;i<=n;i++){
    		f[i]=i;
    	}
    }
    void addedge(int u,int v)
    {
    	e[tot1].v=v;e[tot1].nxt=head[u];
    	e[tot1].flag=0;head[u]=tot1++;
    }
    int find1(int x)
    {
    	return x==f[x]?x:f[x]=find1(f[x]);
    }
    void union1(int x,int y)
    {
    	int fx=find1(x),fy=find1(y);
    	if(fx!=fy)
    		f[fx]=fy;
    }
    void tarjan(int u,int p)
    {
    	low[u]=dfn[u]=++cnt;
    	for(int i=head[u];~i;i=e[i].nxt){
    		int v=e[i].v;
    		if(e[i].flag) continue;
    		e[i].flag=e[i^1].flag=1;
    		if(!dfn[v]){
    			tarjan(v,u);
    			low[u]=min(low[u],low[v]);
    			if(low[v]>dfn[u]){
    				cut[tot].u=u;
    				cut[tot].v=v;
    				tot++;
    			}else{
    				union1(u,v);
    			}
    		}else{
    			low[u]=min(low[u],dfn[v]);
    		}
    	}
    }
    int mx;
    int dfs(int u,int fa)
    {
    	int tmp=0;
    	for(int i=head[u];~i;i=e[i].nxt){
    		int v=e[i].v;
    		if(v==fa) continue;
    		int d=dfs(v,u);
    		mx=max(mx,d+tmp);
    		tmp=max(tmp,d);
    	}
    	return tmp+1;
    }
    
    int main()
    {
    	while(~scanf("%d%d",&n,&m)){
    		if(!n&&!m) break;
    		init(); 
    		int u,v;
    		for(int i=0;i<m;i++){
    			scanf("%d%d",&u,&v);
    			addedge(u,v);
    			addedge(v,u);
    		}
    		for(int i=1;i<=n;i++)
    			if(!dfn[i]) tarjan(i,0);
    		//缩点 建树 
    		memset(head,-1,sizeof(head));//clear 
    		tot1=0; 
    		for(int i=0;i<tot;i++){
    			u=cut[i].u;
    			v=cut[i].v;
    			u=find1(u);//在新树的编号 
    			v=find1(v);
    			addedge(u,v);
    			addedge(v,u);
    		}
    		if(!tot){
    			printf("0\n");
    		}else{
    			mx=0;
    			dfs(find1(cut[0].u),-1);
    			printf("%d\n",tot-mx);
    		}
    	}
    	return 0;
    }
    

    Strongly connected

    HDU - 4635
    题意:给定一个有向图,问加入最多多少边,这个图仍然是不是强连通的,如果这个图本身就是强连通的,输出-1。
    题解:缩点,建图,对于新的图,记录每个新点包含点的个数,从入度为0或出度为0的新点中找出包含点数最小的minnum,再用上面剩余的边ans - minnum*(n-minnum)就是所要的答案。
    (PS:缩点时用stack方法来染色,用并查集在此题不合适,因为是有向图)

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<vector>
    #include<cstdio>
    #include<stack>
    using namespace std;
    #define ll long long
    const int maxn=100010;
    
    
    int low[maxn],dfn[maxn];
    vector<int> ve[maxn];
    struct node{
    	int u,v;
    }cut[maxn];
    int tot,cnt;
    
    int n,m,q;
    int num[maxn];
    int color[maxn],cn;
    bool ins[maxn];
    stack<int> s;
    int in[maxn],out[maxn];
    void init()
    {
    	memset(low,0,sizeof(low));
    	memset(dfn,0,sizeof(dfn));
    	cn=tot=cnt=0;
    	for(int i=0;i<=n;i++){
    		ve[i].clear();
    		ins[i]=color[i]=0;
    		num[i]=in[i]=out[i]=0;
    	}
    	while(!s.empty()) s.pop();
    }
    void tarjan(int u,int p)
    {
    	low[u]=dfn[u]=++cnt;
    	s.push(u);
    	ins[u]=1;
    	for(int i=0;i<ve[u].size();i++){
    		int v=ve[u][i];
    		if(!dfn[v]){
    			tarjan(v,u);
    			low[u]=min(low[u],low[v]);
    			if(low[v]>dfn[u]){
    				cut[tot].u=u;
    				cut[tot].v=v;
    				tot++;
    			}
    		}else if(ins[v]){
    			low[u]=min(low[u],dfn[v]);
    		}
    	}
    	if(low[u]==dfn[u]){
    		cn++;
    		while(s.top()!=u){
    			color[s.top()]=cn;
    			ins[s.top()]=0;
    			s.pop();
    		}
    		color[u]=cn;
    		ins[u]=0;
    		s.pop();
    		
    	}
    }
    
    int main()
    {
    	int t,cas=1;
    	scanf("%d",&t);
    	while(t--){
    		scanf("%d%d",&n,&m);
    		init(); 
    		int u,v;
    		for(int i=0;i<m;i++){
    			scanf("%d%d",&u,&v);
    			ve[u].push_back(v);
    			//ve[v].push_back(u);
    		}
    		for(int i=1;i<=n;i++)
    			if(!dfn[i]) tarjan(i,0);
    
    		for(int i=1;i<=n;i++) num[color[i]]++;
    		printf("Case %d: ",cas++);
    		if(cn==1){
    			//printf("SD\n");//
    			printf("-1\n");
    			continue;
    		}
    		//缩点 建图 
    //		for(int i=0;i<tot;i++){
    //			u=cut[i].u;
    //			v=cut[i].v;
    //			u=color[u];
    //			v=color[v];
    //			in[v]++;out[u]++;
    //		}//不可用上述方法,因为我们这里建的是图,不是割边树 
    		for(int u=1;u<=n;u++){
    			for(int i=0;i<ve[u].size();i++){
    				v=ve[u][i];
    				if(color[u]!=color[v]){
    					out[color[u]]++;
    					in[color[v]]++; 
    				}
    			}
    		} 
    		ll ans=1LL*n*(n-1)-m,res=n;
    		for(int v=1;v<=cn;v++){
    			if(!in[v]||!out[v])
    				res=min(res,1LL*num[v]);
    		}
    		printf("%lld\n",ans-res*(n-res));
    	}
    	return 0;
    }
    

    Caocao’s Bridges

    HDU - 4738
    题意:给定一个无向图,每个边有边权(守护人数),把这个图的一个桥(割边)炸掉,使得图不连通,要求需要人数不少于边权,求最少需要多少人。
    题意:找出所有割边,求其中最小的割边做为答案。
    注意:图本身不联通,答案为0;不存在桥,为-1;桥权值为0,需要一人。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<stack>
    #include<algorithm>
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn=1004;
    const int maxm=1000004;
    
    int n,m;
    struct Edge
    {
    	int v,next,w;
    	bool flag;
    }e[maxm<<1];
    int head[maxn],tot,cnt;
    void addedge(int u,int v,int w)
    {
    	e[tot].v=v;e[tot].flag=0;
    	e[tot].next=head[u];
    	e[tot].w=w;
    	head[u]=tot++;
    }
    int dfn[maxn],low[maxn],ans;
    int color[maxn],cn;
    bool ins[maxn];
    void tarjan(int u)
    {
    	low[u]=dfn[u]=++cnt;
    	ins[u]=1;
    	for(int i=head[u];~i;i=e[i].next){
    		int v=e[i].v;
    		if(e[i].flag) continue;
    		e[i].flag=e[i^1].flag=1;//注意有重边不同权值的情况 ,不能用v!=p	
    		if(!dfn[v]){
    			tarjan(v);
    			low[u]=min(low[u],low[v]);
    			if(dfn[u]<low[v]){
    				ans=min(ans,e[i].w);
    			}
    		}else{//用v!=p过不了,是因为多重边的关系 
    			low[u]=min(low[u],dfn[v]);
    		}
    	}
    }
    void init()
    {
    	memset(low,0,sizeof(low));
    	memset(dfn,0,sizeof(dfn));
    	memset(ins,0,sizeof(ins));
    	memset(head,-1,sizeof(head));
    	tot=cnt=cn=0;
    }
    
    int main()
    {
    	int x,y,w;
    	while(~scanf("%d%d",&n,&m)){
    		if(!n&&!m) break;
    		init();
    		while(m--){
    			scanf("%d%d%d",&x,&y,&w);
    			addedge(x,y,w);addedge(y,x,w);
    		}
    		ans=inf;
    		int k=0;
    		for(int i=1;i<=n;i++)
    			if(!dfn[i]) tarjan(i),k++;
    		if(k>1) printf("0\n"); 
    		else if(ans==inf) printf("-1\n");
    		else if(ans==0) printf("1\n");// 无人守,至少要一人 
    		else printf("%d\n",ans);
    	} 
    	return 0;
    }
    

    Prince and Princess

    HDU - 4685
    题意:给n个王子,m个公主,每个王子匹配多个公主,求在满足最大匹配的情况下,每个王子能选择的公主数即具体的公主。
    题解:求出最大匹配后,设最大匹配数为couple,两边分别建立(n-couple)个虚拟公主和(m-couple)虚拟王子。然后把每个王子匹配上的公主a,向和该王子能匹配的公主bi连边,那么最后能和被匹配上的公主a在同一个强连通分量的公主bi,则表示a能bi替换。
    因为对于同一个连通分量的公主,就相当于她们移位一下她们的匹配王子,能保证最后的匹配数保持最大不变。
    对于要建立虚拟公主、虚拟王子的原因,是为了解决如下样例的问题。
    输入:
    2 2
    1 1
    1 1
    输出:
    1 1
    1 1
    即王子a,b,公主c,d。a、b都能匹配c,但都不能匹配d,如果没有虚拟王子、虚拟公主来凑成完美匹配。那么答案(举例)可能就只有a匹配c,b不能匹配任何公主;这显然是不对的。

    还有,对于这道题,用匈牙利算法求解最大匹配时,如果是王子向公主匹配,即为每个王子找公主的写法,则可以AC;如果是公主向王子匹配,即为每个公主找王子的写法,则会TLE,原因应该是王子向公主的边比较多,(题目说了ki<=500),这样匹配的dfs次数会比较多,时间复杂度高。

    总结:对于二分匹配,一对多的情况下,跑算法时应该是为少的一方找对象,这样求解时间短一些。

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<vector>
    #include<cstdio>
    #include<stack>
    using namespace std;
    #define ll long long
    const int maxn=1010;
    
    
    int low[maxn],dfn[maxn];
    vector<int> ve[maxn];
    int cnt;
    
    int n,m,q;
    int color[maxn],cn;
    bool ins[maxn];
    stack<int> s;
    
    int ly[maxn];
    int lx[maxn];
    bool vis[maxn],mp[maxn][maxn];
    void init()
    {
    	memset(low,0,sizeof(low));
    	memset(dfn,0,sizeof(dfn));
    	cn=cnt=0;
    	for(int i=0;i<=n+m;i++){
    		ve[i].clear();
    		ins[i]=color[i]=0;
    	}
    	while(!s.empty()) s.pop();
    	memset(mp,0,sizeof(mp));
    	memset(ly,-1,sizeof(ly));
    }
    
    bool dfs(int u)
    {
    	for(int v=1;v<=m;v++){
    		if(mp[u][v]&&!vis[v]){
    			vis[v]=1;
    			if(ly[v]==-1||dfs(ly[v])){
    				lx[u]=v;
    				ly[v]=u;
    				return 1;
    			}
    		}
    	}
    	return 0;
    }
    int maxMatch()
    {
    	int ans=0;
    	for(int i=1;i<=n;i++){
    		memset(vis,0,sizeof(vis));
    		if(dfs(i)) ans++;
    	}
    	return ans;
    }
    
    
    void tarjan(int u)
    {
    	low[u]=dfn[u]=++cnt;
    	s.push(u);
    	ins[u]=1;
    	for(int i=0;i<ve[u].size();i++){
    		int v=ve[u][i];
    		if(!dfn[v]){
    			tarjan(v);
    			low[u]=min(low[u],low[v]);
    		}else if(ins[v]){
    			low[u]=min(low[u],dfn[v]);
    		}
    	}
    	if(low[u]==dfn[u]){
    		cn++;
    		while(s.top()!=u){
    			color[s.top()]=cn;
    			ins[s.top()]=0;
    			s.pop();
    		}
    		color[u]=cn;
    		ins[u]=0;
    		s.pop();
    		
    	}
    }
    int main()
    {
    	int t,cas=1;
    	scanf("%d",&t);
    	while(t--){
    		scanf("%d%d",&n,&m);
    		init();
    		int u,v,k;
    		for(int u=1;u<=n;u++){
    			scanf("%d",&k);
    			while(k--){
    				scanf("%d",&v);
    				mp[u][v]=1;
    			}
    		}
    		int couple=maxMatch();
    
    		int N=n+m-couple;
    		for(int i=n+1;i<=N;i++){
    			for(int j=1;j<=N;j++){
    				mp[i][j]=1;
    			}
    		}
    		for(int i=m+1;i<=N;i++){
    			for(int j=1;j<=N;j++){
    				mp[j][i]=1;
    			}
    		}
    		int n1=n,m1=m;
    		n=m=N;
    		memset(ly,-1,sizeof(ly));//---------
    		memset(lx,-1,sizeof(lx));
    		couple=maxMatch();
    
    		
    		for(int i=1;i<=n;i++){
    			for(int j=1;j<=m;j++){
    				if(mp[i][j]&&lx[i]!=j){
    					ve[lx[i]].push_back(j);
    				}
    			}
    		}
    		
    		for(int i=1;i<=n;i++)	
    			if(!dfn[i]) tarjan(i);
    		n=n1;m=m1;
    		vector<int> cur;
    		printf("Case #%d:\n",cas++);
    		for(int i=1;i<=n;i++){
    			cur.clear();
    			for(int j=1;j<=m;j++){
    				if(mp[i][j]&&color[lx[i]]==color[j])//mp[j][i]&&
    					cur.push_back(j);
    			}
    			printf("%d",(int)cur.size());
    			for(int j=0;j<cur.size();j++)
    				printf(" %d",cur[j]);
    			printf("\n");
    		}
    	}
    	return 0;
    }
    
    展开全文
  • 连通图小结

    2016-01-30 01:01:21
    连通图小结 A Summary for ConnectedGraph连通图小结\ A\ Summary\ for\ Connected GraphI.概念I.概念 强连通 强连通:有向图中(u,v)(u,v)存在u→v, v→uu\to v,\ v\to u的两条路径,称(u,v)(u,v)为强连通 强...
  • 极大极小连通图

    2021-05-12 22:13:16
    (非连通图的极大连通子图叫做连通分量,每个分量是一个连通图)3.称为极大是因为如果此时加入任何一个不在图的点集中的点都会导致它不再连通。下图为非连通图,图中有两个极大连通子图(连通分量)。在这里插入...
  • 图例: ... 普里姆算法:假设N={v,{E}}是连通图,TE是N上的最小生成中边的集合,算法从U={u0}(u0属于V),TE={}开始,重复执行下述操作:  在所有u属于U,v属于V-U的边属于E中找一条代价最
  • 无向图,连通图

    万次阅读 2019-03-04 13:52:55
    **一、 (Graph)**是由顶点(vertex)的有穷非空集合和顶点之间边(edge)的集合组成,通常表示为:G(V,E),其中,G表示一个,V是G中顶点的...
  • 求无向连通图的最小生成算…

    千次阅读 2016-01-14 09:11:18
    最小生成是图论里很重要的部分。但是由于它属于图论所以NOIP基本不考,对于NOI又太基础,所以竞赛中出现的几率比较小,即使要考也不可能考裸的生成算法= ...对于G=(V,E),用Prim算法求最小生成
  • 最近在复习数据结构和算法的的内容,栈和队列的思想是比较深刻,借于许多高级语言...一般可用节点结构体来封装一个节点,但是图,图的话就不容易表示了,因为图是无序的,每个节点与其他节点有任意的连通性。...
  • 题意:给出n个人和他们的坐标,闪电随机劈到一个机器人,在他周围的与他距离不超过r的机器人会被传播,但是三点共线的情况只能传染最近的那个,传染后的有...对于任何一个顶点数为n的无向连通图,我们列出一个矩阵。
  • 求无向连通图的最小生成算法——Prim与Kruskal及相关优化 数据结构课程 最小生成是图论里很重要的部分。但是由于它属于图论所以NOIP基本不考,对于NOI又太基础,所以竞赛中出现
  • 连通图的强连通分支

    千次阅读 2011-09-28 19:28:06
    //双连通分量方法一: //定义一:给定的有向图G=(V,...//互相到达,则称G是强连通图。 //定义二:有向图的极大强连通子图称为强连通分支。 //由定义可2以得知有向图的强连通分支是一个最大的顶点集合,在这个集合中
  • 题意:有n个城市,城市之间有n-1条路连接每个城市,也就是说...导弹不能运到一起就是说任何两个导弹不能在一个连通图中,所以我们的任务就是用最少的代价摧毁一些路使m个导弹分别在m个连通图中。 这题是就反面,最少的
  • 如果此图是有向图,则称为强连通图(注意:需要双向有路径)。 简单的来讲就是, 强连通的定义是:有向图 G 强连通是指,G 中任意两个结点连通。 强连通分量(Strongly Connected Components,SCC
  • 1知识点:判断一个连通无向的最小生成是否是唯一的+最小生成_Prim算法+记录路径 2题意:给定一个连通无向,判断这个连通无向的最小生成是否是唯一的 3错误反思: 4思路: 1>思路1:第一遍Prim算法求...
  • 无向连通图的割点

    2019-10-28 22:57:17
    求一个无向连通图的割点。 割点的定义: 若除去此结点和与其相关的边,无向连通图不再连通。 最简单直接的办法: 利用BFS或DFS可以用来判断图连通性的性质(即根据一次深搜或广搜能否遍历图所有的顶点来...
  • 这是一个不正经与简单明了的笔记 ...【连通图】图中的任意两点,有路可以连通 例子: 1. 将 顶点a 与 a的所有边删除 =&amp;amp;amp;amp;gt; 图被分成两个部分(连通分量) =&a
  • 连通图的算法

    千次阅读 2014-10-12 23:57:08
    说到以Tarjan命名的算法,我们经常提到的有3个,其中就包括本文所介绍的求强连通分量的Tarjan算法。...在一个强连通图中,任意两个点通过一定路径互相连通。比如图一是一个强连通图,而图二不是。因为没
  • //连通图的深度优先生成中关节点特性: //1.若生成的根有两棵或两棵以上的子树,则此根顶点必为关节点,因为图中不存在联结不同子树中顶点的边; //2.若生成中某个非叶子顶点,其某棵子树的结点均没有指向该...
  • 给定一棵T,中每个顶点u有权值w(w),可以是负数。现在要找到T的一个连通子图使该子图的权之和最大。对于给定的T,计算T的最大连通分支。
  • 有向连通图的割点

    千次阅读 2013-09-01 22:01:30
    连通图:有向图 G=(V,E) 中,若对于V中任意两个不同的顶点 x 和 y ,存在从x 到 y 以及从 y 到 x 的路径,则称 G 是强连通图(Strongly Connected Graph)。相应地有强连通分量(Strongly Conne
  • 图论(3):连通图和匹配度 文章目录图论(3):连通图和匹配度1.顶点连通度定义2.边连通度定义3.顶点连通度、边连通度、最小度的关系①定理②定理③n-顶点连通、n-边连通定义 1.顶点连通度定义 ​ 设 G=(V,E) 是一个无向...
  • 连通图的割点、割边 连通图的割点、割边(桥)、块、缩点,有向图的强连通分量 一、基本概念 无向图 割点:删掉它之后(删掉所有跟它相连的边),图必然会分裂成两个或两个以上的 子图。 块:没有割点的连通子图 割边:...
  • 图的连通图,连通分量的分析和代码实现。
  • LZ研究过PRIM和KRUSKAL算法,发现两种算法只能对强连通图或者无向连通图(本质相同)处理,但是单向连通图和弱连通图不满足从任何一点出发可到达任何顶点,所以LZ认为单向连通图和弱连通图不能用最小生成算法,...
  • 极大连通子图与极小连通子图(带讲解)

    万次阅读 多人点赞 2018-12-29 15:29:10
    首先我们先对什么连通图做一个基本了解 连通图

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,158
精华内容 6,463
关键字:

任何树都是连通图