精华内容
下载资源
问答
  • 桥的概念:无向连通图中,删掉某条边可以使原图不连通,那么该边就是无向图的桥。 tarjan算法求桥的思想简单说一下:以任意一点开始建立搜索树,记录每点的搜索深度dep和非父子边能到达的最早节点

    hdoj 4738

    题意:有n个点m条边,问如果删掉一条边使图不连通,问最少需要多少兵力。每条边都有驻守的士兵,如果想删掉这条边至少要派相同人数的士兵。

    思路:就是一个连通图求最小权的桥的问题。

    桥的概念:无向连通图中,删掉某条边可以使原图不连通,那么该边就是无向图的桥。

    tarjan算法求桥的思想简单说一下:以任意一点开始建立搜索树,记录每个点的搜索深度dep和非父子边能到达的最早节点深度low,就是说这条路上可能有一个环,这个环里的最小的搜索深度就是low,如果没有环,那么dep=low(父子边成环)。

    解题思路:这个题比较裸但是坑点比较多,首先图可能是不连通的,要先判断一下,我是用的并查集,如果本身就不连通,输出0即可;如果某条边守卫为0,也应该派1个被炸药的过去。。。

    写了个模板留着以后用。

    PS:这个题的内存限制开的有点小,应该说网上大部分题解的代码都过不了,因为边最多有100w条,记双向边又要200w,一个结构体或类里存4~5个int,能过才有鬼。

    之所以没有mle是因为hdoj的判题机制貌似是看程序运行实际用到了多少内存,而不是声明了多少内存。

    (我也没别的意思就是吐槽一下因为我太蠢写了个没用的memset结果mle了好久。。。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int M = 1005;
    
    struct Edge{
        int to, next, id, val;
        Edge(){}
        Edge(int a, int b, int c, int d): to(a), next(b), id(c), val(d){}
    }edge[M * M * 2];
    int _next[M], edgeCnt, dep[M], low[M], nowdep, bridge[M * M * 2];
    bool isBridge[M * M];
    void addEdge(int from, int to, int val, int id){
        edge[++edgeCnt] = Edge(to, _next[from], id, val);
        _next[from] = edgeCnt;
        edge[++edgeCnt] = Edge(from, _next[to], id, val);
        _next[to] = edgeCnt;
    }
    void tarjanInit(){
        memset(dep, 0, sizeof dep);
        memset(low, 0, sizeof low);
        memset(isBridge, 0, sizeof isBridge);
        nowdep = 0;
    }
    void tarjan(int from, int id) {
        dep[from] = low[from] = ++nowdep;
        for(int i = _next[from]; i; i = edge[i].next){
            if(edge[i].id == id) continue;
            int to = edge[i].to;
            if(!dep[to]){
                tarjan(to, edge[i].id);
                low[from] = min(low[from], low[to]);
                if(dep[from] < low[to]) isBridge[i] = true;
            }
            else low[from] = min(low[from], dep[to]);
        }
    }
    int tarjanGetBridge() {
        tarjanInit();
        tarjan(1, 0);
        int cnt = 0;
        for(int i = 1; i <= edgeCnt; i++)
            if(isBridge[i]) bridge[cnt++] = i;
        return cnt;
    }
    /
    int father[M];
    void init() {
        for(int i = 1; i <= M; i++) father[i] = i;
     //   memset(edge, 0, sizeof edge);(╯‵□′)╯︵┴─┴ 
        memset(_next, 0, sizeof _next);
        edgeCnt = 0;
    }
    int getfather(int a) {
        return a == father[a] ? a : father[a] = getfather(father[a]);
    }
    int unit(int a, int b){
        int t1 = getfather(a), t2 = getfather(b);
        father[t1] = min(t1, t2);
        father[t2] = min(t1, t2);
    }
    main() {
        int n, m;
        while(~scanf("%d %d", &n, &m)){
            if(n == 0 && m == 0) break;
            init();
            for(int i = 1; i <= m; i++) {
                int a, b, c;
                scanf("%d %d %d", &a, &b, &c);
                addEdge(a, b, c, i);
                unit(a, b);
            }
            bool flag = true;
            for(int i = 1; i <= n; i++) if(getfather(i) != father[1]) flag = false;
            if(!flag){
                puts("0");
                continue;
            }
            int cnt = tarjanGetBridge();
            int ans = 0x7fffffff;
            for(int i = 0; i < cnt; i++) {
                ans = min(ans, edge[bridge[i]].val);
            }
            if(ans == 0) puts("1");
            else if(ans == 0x7fffffff) puts("-1");
            else printf("%d\n", ans);
        }
    }
    


    展开全文
  • 给出一个nn个点,mm条边的无向图,求图的割点。 输入格式 第一行输入n,mn,m 下面mm行每行输入x,yx,y表示xx到yy一条边 输出格式 第一行输出割点个数 第二行按照节点编号从小到大输出节点,用空格隔开 输入...

    题目背景

    割点

    题目描述

    给出一个nn个点,mm条边的无向图,求图的割点。

    输入格式

    第一行输入n,mn,m

    下面mm行每行输入x,yx,y表示xx到yy有一条边

    输出格式

    第一行输出割点个数

    第二行按照节点编号从小到大输出节点,用空格隔开

    输入输出样例

    输入 #1

    6 7
    1 2
    1 3
    1 4
    2 5
    3 5
    4 5
    5 6

    输出 #1

    1 
    5

    说明/提示

    对于全部数据,n \le 20000n≤20000,m \le 100000m≤100000

    点的编号均大于00小于等于nn。

    tarjan图不一定联通。

    套用Tarjan模板:

    #include<iostream>
    #include<cstdio>
    #include<vector>
    #include<cstring>
    #include<stack>
    #include<queue>
    #include<map>
    #include<set> 
    #include<algorithm>
    using namespace std;
    #define lowbit(x) (x&-x)
    #define mem(a,b) memset(a,b,sizeof(a))
    #define eps 1e-9
    #define INF 999999
    #define MAXN 20005
    //struct edge{
    //	int to;
    //	//int val;
    //};
    //int next[MAXN]; 
    vector<int> G[MAXN];
    int dfn[MAXN],low[MAXN];
    bool instack[MAXN];
    set<int> ans;		//存储割点 
    //stack<int> s;				
    int timing;				//时间戳 
    int color[MAXN];		//代表当前结点所属第几个scc 
    int colorcnt[MAXN];		//代表第某个scc有几个结点 
    int cnt;				//scc个数 
    int V,E;				
    
    void init()
    {
    	for(int i=0;i<=V;i++)
    		G[i].clear();
    	ans.clear();
    	mem(dfn,0);
    	mem(color,0);
    	mem(colorcnt,0);
    	mem(instack,false);
    	mem(low,0);
    	timing=cnt=0;
    }
    
    //割点 
    void tarjan(int u,int rt)
    {
    	++timing;
    	low[u]=dfn[u]=timing;
    	int child=0;
    	for(int i=0;i<G[u].size();i++)
    	{
    		int v=G[u][i];
    		if(dfn[v]==0)
    		{
    			child++;
    			tarjan(v,rt);
    			low[u]=min(low[u],low[v]);
    			if(u!=rt && low[v]>=dfn[u]){
    				ans.insert(u);
    			}
    		}
    		low[u]=min(low[u],dfn[v]);
    	}		
    	if(child>=2&&u==rt){
    		ans.insert(u);
    	}
    }
    
    int main()
    {
    	ios::sync_with_stdio(false);
    	cin >> V >> E;
    	int x,y;
    	for(int i=1;i<=E;i++)
    	{
    		cin >> x >> y;
    		G[x].push_back(y);
    		G[y].push_back(x);
    	}
    	for(int i=1;i<=V;i++){
    		if(dfn[i]==0)
    			tarjan(i,i);
    	}
    	cout << ans.size() << endl;
    	set<int>::iterator ite;
    	for(ite=ans.begin();ite!=ans.end();ite++)
    		cout << *ite << " ";
    	cout << endl;
    	return 0;
    }

     

    展开全文
  • 二分图的判定问题比较少见,简单来说,就是对于给定的图,判断...无向图 G 为二分图的充分必要条件:G 至少顶点,且其所有回路的长度均为偶数。 int n;//节点数 vector&lt;int&gt; G[N];//G[i]表示i...

    二分图的判定问题比较少见,简单来说,就是对于给定的图,判断图是否为二分图。

    可以把每个节点着以黑色和白色之一,使得每条边的两个端点颜色不同,不难发现,对于一个当且仅当每个连通分量都是二分图,因此我们只考虑无向连通图。

    无向图 G 为二分图的充分必要条件:G 至少有两个顶点,且其所有回路的长度均为偶数。

    int n;//节点数
    vector<int> G[N];//G[i]表示i节点邻接的点
    int color[N];//color[i]=0,1,2 表i节点不涂颜色、涂白色、涂黑色
    bool bipartite(int u)//判断无向图是否可二分
    {
        for(int i=0;i<G[u].size();i++)//枚举结点
        {
            int v=G[u][i];//相邻节点
            if(color[v]==color[u])//若两结点颜色相同,无法二分
                return false;
            if(!color[v])//若结点没涂颜色
            {
                color[v]=3-color[u];//改变结点颜色,使v的颜色与u的颜色对立
                if(!bipartite(v))//若点v不满足二分图话,则无法二分
                    return false;
            }
        }
        return true;
    }
     
    
    展开全文
  • 树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。 给你一棵包含n个节点的数,标记为0到n - 1 。给定数字n和一个有 n - 1 条无向边的 edges列表(每一个...

    题目描述

    树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。

    给你一棵包含 n 个节点的数,标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表(每一个边都是一对标签),其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。

    可选择树中任何一个节点作为根。当选择节点 x 作为根节点时,设结果树的高度为 h 。在所有可能的树中,具有最小高度的树(即,min(h))被称为 最小高度树 。

    请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

    树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

    提示:

    1 <= n <= 2 * 104
    edges.length == n - 1
    0 <= ai, bi < n
    ai != bi
    所有 (ai, bi) 互不相同
    给定的输入 保证 是一棵树,并且 不会有重复的边

    拓扑排序

    连续两天做了3道拓扑排序的题目,有一些心得

    拓扑排序--原型

    拓扑排序--原型--直接实现:

    它是一个 DAG 图,那么如何写出它的拓扑排序呢?这里说一种比较常用的方法:

    实现步骤:

    STEP1 从 DAG 图中选择一个 没有前驱(即入度为0)的顶点并输出。

    STEP2 从图中删除该顶点和所有以它为起点的有向边。

    STEP3 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

    复杂度分析:

    直接实现的话,每删除一个结点循环一次(共n次),每次循环都需要遍历整个图寻找无前驱结点,遍历图的复杂度为O(n^2),所以总复杂度为O(n^3)

    拓扑排序--原型--栈实现:

    心得: 我发现,算法的逻辑可以用一些简单的逻辑来等效,从而降低复杂度

    等效过程:

    STEP1 从 DAG 图中选择一个 没有前驱(即入度为0)的顶点并输出。

    STEP1 等效为--> 扫描顶点表,将没有前驱(即入度为0)的顶点压栈

    STEP2 从图中删除该顶点和所有以它为起点的有向边。

    STEP2.1 "删除该顶点" 等效为-->在 "判断结点是否被访问的数组"(boolean[] isTraveled) 中 ,标记为已访问

    STEP2.2 "删除所有以它为起点的有向边" 等效为-->在 "入边统计"数组"(int[] nodeInEdgeCount) 中 ,将以顶点index为起点 的 各个邻接点 的 入度 减1;

    等效后,算法所需要使用的所有辅助数据结构如下

    //辅助数据结构
            int[][] graph = new int[numCourses][numCourses];//图的邻接矩阵
            int[] nodeInEdgeCount = new int[numCourses];//"入边统计"数组
            Stack<Integer> zeroInStack = new Stack<>();//入度为0的结点栈
            boolean[] isTraveled = new boolean[graph.length];//判断结点是否被访问的数组,被访问记为true
            int countTravel = 0;//已经被访问的结点个数

    实现步骤:

    扫描顶点表,将没有前驱(即入度为0)的顶点压栈;
    当栈S非空时循环
    3.1 退出栈顶元素index;输出栈顶元素index;累加器加1;
    3.2 将以顶点index为起点 的 各个邻接点 的 入度 减1; (从图中删除该顶点和所有以它为起点的有向边。)
    3.3 将新的入度为0的顶点入栈;
    if (count<vertexNum) 输出有回路信息;

    复杂度分析:

    在"直接实现"的基础上省略了 "每次循环都需要遍历整个图寻找无前驱结点" 这个过程 ,复杂度为O(n^2)

    拓扑排序--变式(本题)--栈实现

    修改的点:

    1 本题是无向图,而 拓扑排序--原型 是有向图

    2 本题是删除 [边数]为1 的点 ,而不是"入度"为1 的点

    3 因为本题可能会有多个"最小高度树根结点"需要输出,所以不能一个个地删除粗结点,

    所以需要像 "二叉树层序遍历--带层数计数" 的实现方式一样,一次性删除一整层的所有 [边数]为1 的结点

    实现步骤+等效逻辑:

    STEP1 初始化"储存只有一条边的结点的栈" 找到[边数]为1的所有结点

    STEP2 循环

    STEP2.1 一次性把所有队列中[边数]为1的结点出队,
    出队的同时 把该[结点]删除,把与该结点有关的[边]删除
    STEP2.1.1 把该[结点]删除-->等效为 把 结点i 标记为已访问 isTraveled[i]=true
    STEP2.1.2 把与该结点有关的[边]删除-->等效为 把 结点i 相连接的其余所有结点的边数减1 for(){ edgeCount[j]-=1; }

    STEP2.2 把新的[边数]为1的结点入队
    STEP2.2 把新的[边数]为1的结点入队-->等效为 把 edgeCount==1&&isTraveled[]==false 的结点入队

    STEP2.3 如果剩余未被访问结点数 等于 [边数]为1的结点数,则返回剩余未被访问结点(他们就是最小高度树的树根,可能有很多个)
    STEP2.3 -->等效为 返回 当前[边数]为1的结点的list
     

    拓扑排序总结

    拓扑排序本质上是针对 "边" 进行的一种操作, 这让我不禁深入思考,还可以有什么别的针对"边"的操作?

    一个结点的边有如下性质

    1 有几条边

    2 出度/入度

    3 边的长度

    4 边可删除

    比如:

    1访问结点后删除边 (边条数改变)(入度/出度 改变)

    2每轮循环访问"符合边数要求"的结点 (边条数判断)(入度/出度 判断)

    几个值得思考的问题

    对于 栈/队列 这种辅助数据结构

    是出栈访问,还是入栈访问?--以及重复入栈的问题

    //入队就标记为已访问(出队时才标记已经访问的话,会导致重复入队),(因为有 1.出队判定为访问 和 2.入队判定为访问 两大流派)后来我总结了这个重复入队的问题根源,那就是"在哪里判断了是否已经入队""就在哪里更新"入队判断符号"",比如在这里进行了if(isTraveled[i]==false)判断,就要在这里更新入队判断符isTraveled[i]=true;

     

    实现代码

    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    //编程思维
    //线性思维,顺序思维
    //让人类理解编程思维(人机工效)
    //在脑子里想象一张程序框图
    class Solution {
        public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            //建立辅助数据结构
            int[] edgeCount = new int[n];//结点[边数]统计数组 下标为i的格子储存着下标为i的结点的[边数]
            boolean[] isTraveled = new boolean[n];//结点是否被访问数组 被访问为true
            int travelCount = 0;//被访问的结点个数计数器
            Queue<Integer> oneEdgeQueue = new LinkedList<>();//当前[边数]为1的结点的队列queue
            List<Integer> oneEdgeList = new LinkedList<>();//当前[边数]为1的结点的list
            //输入处理
            //根据prerequisite和numCourses建立图
            boolean[][] graph = new boolean[n][n];
            for(int i=0;i<edges.length;i++){
                int startNode = edges[i][1];
                int endNode = edges[i][0];
                graph[endNode][startNode] = true;
                graph[startNode][endNode] = true;
                edgeCount[startNode] += 1;
                edgeCount[endNode] += 1;
            }
    
            //STEP1 初始化"储存只有一条边的结点的栈" 找到[边数]为1的所有结点
            int oneEdgeNodeCount_ = 0;
            for(int i=0;i<n;i++){
                int countEdge_temp = 0;
                for(int j=0;j<n;j++){
                    if(graph[i][j]==true){
                        countEdge_temp += 1;
                    }
                }
                if(countEdge_temp<=1 && isTraveled[i]==false){//如果[边数]为1
                    oneEdgeQueue.offer(i);
                    isTraveled[i]=true;
                    travelCount+=1;
                    oneEdgeList.add(i);
                    oneEdgeNodeCount_+=1;
                }
            }
            int noTraveledCount_ = n;//剩余未被访问结点数
            if(noTraveledCount_ == oneEdgeNodeCount_){
                return oneEdgeList;
            }
            //STEP2 循环
            while(true){
                //STEP2.1 一次性把所有队列中[边数]为1的结点出队,
                //出队的同时 把该[结点]删除,把与该结点有关的[边]删除
                //STEP2.1.1 把该[结点]删除-->等效为 把 结点i 标记为已访问 isTraveled[i]=true
                //STEP2.1.2 把与该结点有关的[边]删除-->等效为 把 结点i 相连接的其余所有结点的边数减1 for(){ edgeCount[j]-=1; }
                int nowQueueSize = oneEdgeQueue.size();//需要提前获取队列的大小,否则删除过程中由于队列大小缩小,会出错
                for(int i=0;i<nowQueueSize;i++){
                    int index = oneEdgeQueue.poll();
                    System.out.println(index);
                    //STEP2.1 出队的同时 把该[结点]删除,把与该结点有关的[边]删除
                    //STEP2.1.2 把与该结点有关的[边]删除-->等效为 把 结点i 相连接的其余所有结点的边数减1 for(){ edgeCount[j]-=1; }
                    for(int j=0;j<n;j++){
                        if(graph[index][j]==true){//把 结点i 相连接的其余所有结点的边数减1
                            edgeCount[j]-=1;
                        }
                    }
                }
                //STEP2.2 把新的[边数]为1的结点入队
                //STEP2.2 把新的[边数]为1的结点入队-->等效为 把 edgeCount==1&&isTraveled[]==false 的结点入队
                int oneEdgeNodeCount = 0;
                int travelCount_old = travelCount;
                oneEdgeList = new LinkedList<>();//刷新list "当前[边数]为1的结点的list"
                for(int i=0;i<edgeCount.length;i++){
                    if(edgeCount[i]<=1 && isTraveled[i]==false){
                        oneEdgeQueue.offer(i);
                        isTraveled[i]=true;//入队就标记为已访问(出队时才标记已经访问的话,会导致重复入队),(因为有 1.出队判定为访问 和 2.入队判定为访问 两大流派)后来我总结了这个重复入队的问题根源,那就是"在哪里判断了是否已经入队""就在哪里更新"入队判断符号"",比如在这里进行了if(isTraveled[i]==false)判断,就要在这里更新入队判断符isTraveled[i]=true;
                        travelCount+=1;
                        oneEdgeNodeCount+=1;
                        oneEdgeList.add(i);
                    }
                }
                //现在思考在最后的情景
                //STEP2.3 如果剩余未被访问结点数 等于 [边数]为1的结点数,则返回剩余未被访问结点(他们就是最小高度树的树根,可能有很多个)
                //STEP2.3 -->等效为 返回 当前[边数]为1的结点的list
                int noTraveledCount = n - travelCount_old;//剩余未被访问结点数
                if(noTraveledCount == oneEdgeNodeCount){
                    return oneEdgeList;
                }
                //System.out.println("一轮结束");
    
            }
        }
    
        public static void main(String[] args) {
            Solution s = new Solution();
            //int[][] grap = {{3,0},{3,1},{3,2},{3,4},{5,4}};//6
            //int[][] grap = {{0,1}};//2
            //int[][] grap = {{1,0},{1,2},{1,3}};//4
            int[][] grap = {};//1
            List<Integer> a = s.findMinHeightTrees(1,grap);
            System.out.println(a);
    
        }
    }

    惨烈的AC结果...至少是自己做的

    展开全文
  • 且仅有一个特定的称为根(root)的结点。 (2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,....,Tm, 其中每一个集合本身又是一棵树,并且称为根的...
  • 4、完全n个节点的无向完全|有向完全 5、度、出度和入度(顶点数、边数与各顶点的度之间的关系) 6、路径:回路或环|简单路径 7、子图 8、连通图连通分量 9、强连通图和强连通分量 10、网 11、
  • 求出有n个点的有标号简单连通无向图的数目。 题解 什么破玩意,直接输出\(2^{C_n^2}\)走人 我们发现这张图要求连通,而上式肯定不能保证连通。 其实上式表示的是不保证连通的有标号简单无向图。 就差在一个连通上啊...
  • 离散数学第12章树

    2021-01-09 16:56:36
    结论:树都是简单无向图,连通,无圈,m = n-1 连通无圈 无自环且每对节点之间的基本链唯一 基本链说明连通,基本链唯一再加上无自环就是无圈 连通,加一边仅会导致有一个圈 如果加一条边会两个圈,那么去掉...
  • 数据结构-树的类别

    2019-04-17 11:19:41
    棵树有N个节点,那一定有n-1条边 二叉树 含义:含义每个节点只有两个子节点的树,时间复杂度为O(log n) 完全二叉树 含义:二叉树的高度为h时,1~h-1层的节点数达到最大数,第h层从左往右连续缺少节点的二叉树 ...
  • LeetCode 310 最小高度树

    2021-01-11 17:30:52
    树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一 棵树。 给你一棵包含 n 个节点的数,标记为 0 到 n - 1 。给定数字 n一个有 n - 1 条无向边的 edges ...
  • 题意:给你一个n点m边无向图。你需要给每一个边定向,然后必须让所给的k对点是可达的。 题解: 首先明确一点,我们通过边定向,是可以将一个无向图边双连通块构成一个连通块的。构造方法也很简单,直接在块内dfs,...
  • 树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。 给你一棵包含 n 个节点的数,标记为 0 到 n - 1 。给定数字 n一个有 n - 1 条无向边的 edges 列表...
  • 310. 最小高度树

    2020-12-28 22:15:59
    树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。 给你一棵包含 n 个节点的数,标记为 0 到 n - 1 。给定数字 n一个有 n - 1 条无向边的 edges 列表...
  • 310 最小高度树

    2020-11-24 14:28:40
    树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。 给你一棵包含 n 个节点的数,标记为 0 到 n - 1 。给定数字 n一个有 n - 1 条无向边的 edges 列表...
  • 树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,一个任何没有简单环路的连通图都是一棵树。 给你一棵包含 n 个节点的数,标记为 0 到 n - 1 。给定数字 n一个有 n - 1 条无向边的 edges 列表...
  • 给一个N个点M条边的连通无向图,满足每条边最多属于一个环,Q组询问,每次询问两点之间的最短路径。 analysis 建出圆方树后,可以知道仙人掌上每一个方点连着的边双其实就是一个简单环 tarjantarjantarjan缩...
  • 入门学习Linux常用必会60命令实例详解doc/txt

    千次下载 热门讨论 2011-06-09 00:08:45
    hda1中的“1”代表hda的第一个硬盘分区 (partition),hda2代表hda的第二主分区,第一个逻辑分区从hda5开始,依此类推。此外,可以直接检查 /var/log/messages文件,在该文件中可以找到计算机开机后系统已辨认出来的...
  • 给定一个n个点、m条边的无向图。保证图是连通的,且m≥n-1。 以首都(1节点)为根节点生成最小树。树的值定义为每个节点的深度和(根节点深度0)。举个例子: 而我们知道,可能多种情况使树的权值最小,题目给...
  • PAT 1013 C++ 版

    2019-02-12 20:42:49
    给出一个查询数据,判断如果从图中去掉这个顶点,以及这个顶点外的所有边时,求:还需要几条边使得这个无向图连通? 如果不需要任何边,则输出0;如果的话,则输出需要的边数n。 2.分析 题目比较简单。 涉及到无向...
  • 如果棵树有N个节点,可以证明其有且仅有N-1 条边。 路径:棵树上,任意两个节点之间最多有简单路径。我们用 dis(a,b) 表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。 直径:...
  • [bzoj3124][乱搞]直径

    2018-04-21 15:22:29
    如果棵树有N个节点,可以证明其有且仅有N-1 条边。 路径:棵树上,任意两个节点之间最多有简单路径。我们用 dis(a,b) 表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。 直径:...
  • 如果棵树有N个节点,可以证明其有且仅有N-1 条边。 路径:棵树上,任意两个节点之间最多有简单路径。我们用 dis(a,b)表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。 直径:棵树上...
  • 如果棵树有N个节点,可以证明其有且仅有N-1 条边。 路径:棵树上,任意两个节点之间最多有简单路径。我们用 dis(a,b)表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。 直径:棵树上...
  • 如果棵树有N个节点,可以证明其有且仅有N-1条边。 路径:棵树上,任意两个节点之间最多有简单路径。我们用dis(a,b)表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离...
  • [SDOI2013] 直径

    2018-08-22 10:35:00
    如果棵树有N个节点,可以证明其有且仅有N-1 条边。 路径:棵树上,任意两个节点之间最多有简单路径。我们用 dis(a,b)表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。 直径:棵树上...
  • [BZOJ3124]直径

    2018-07-31 21:06:00
    如果棵树有N个节点,可以证明其有且仅有N-1条边。 路径:棵树上,任意两个节点之间最多有简单路径。我们用dis(a,b)表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。直径:棵树上,...
  • 如果棵树有N个节点,可以证明其有且仅有 N-1 条边。 路径:棵树上,任意两个节点之间最多有简单路径。我们用 dis(a,b)表示点 a 和点 b 的路径上各边长度之和。称 dis(a,b)为 a、b 两个节点间的距离。 直径...

空空如也

空空如也

1 2 3 4
收藏数 62
精华内容 24
关键字:

一个简单连通无向图有n个节点