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有一条边

输出格式

第一行输出割点个数

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

输入输出样例

输入 #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<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 列表（每一个边都是一对标签），其中 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结果...至少是自己做的