小总结 – hahaschool

生成树小总结

August 31, 20152015-08-31hahaschoolLeave a comment

无向图最小生成树

Prim算法

这个实现做的非常不好，需要改进。对付稠密图，Prim更胜Kruskal一筹。

struct Node{
    vector<int> to;
    vector<int> cost;
    int mi;
    int parent;
    bool vis;
    void init(){
        to.clear();
        cost.clear();
        mi = 0x3f3f3f3f;
        vis = false;
        parent = -1;
    }
    void addEdge(int _to, int _cost){
        to.push_back(_to);
        cost.push_back(_cost);
    }
} vertex[100005];

   int n = 0, m = 0;
struct snode{
    int key;
    int v;
    friend bool operator < (snode a,snode b){
        return a.key > b.key;
    }
}sn[100005];
struct Node_cmp{
    bool operator () (int &a, int &b){
        return vertex[a].mi > vertex[b].mi;
    }
};

void MST_Prim(){
    for (int i = 1; i <= n ; i++) {
        sn[i].key = 0x3f3f3f3f;
        sn[i].v = i;
    }
    priority_queue<snode> que;
    sn[1].key = 0;
    que.push(sn[1]);
    while (!que.empty()) {
        int cur = que.top().v;
        que.pop();
        if(vertex[cur].vis){
            continue;
        }
        vertex[cur].vis = true;
        for (int i = 0; i < vertex[cur].to.size(); i++) {
            int nxt = vertex[cur].to[i];
            if (!(vertex[nxt].vis) && vertex[cur].cost[i] < sn[nxt].key) {
                sn[nxt].key = vertex[cur].cost[i];
                vertex[nxt].parent = cur;
                que.push(sn[nxt]);
            }
        }
    }
}

struct Node{

vector<int> to;

vector<int> cost;

int mi;

int parent;

bool vis;

void init(){

to.clear();

cost.clear();

mi = 0x3f3f3f3f;

vis = false;

parent = -1;

}

void addEdge(int _to, int _cost){

to.push_back(_to);

cost.push_back(_cost);

}

} vertex[100005];

int n = 0, m = 0;

struct snode{

int key;

int v;

friend bool operator < (snode a,snode b){

return a.key > b.key;

}

}sn[100005];

struct Node_cmp{

bool operator () (int &a, int &b){

return vertex[a].mi > vertex[b].mi;

}

};

void MST_Prim(){

for (int i = 1; i <= n ; i++) {

sn[i].key = 0x3f3f3f3f;

sn[i].v = i;

}

priority_queue<snode> que;

sn[1].key = 0;

que.push(sn[1]);

while (!que.empty()) {

int cur = que.top().v;

que.pop();

if(vertex[cur].vis){

continue;

}

vertex[cur].vis = true;

for (int i = 0; i < vertex[cur].to.size(); i++) {

int nxt = vertex[cur].to[i];

if (!(vertex[nxt].vis) && vertex[cur].cost[i] < sn[nxt].key) {

sn[nxt].key = vertex[cur].cost[i];

vertex[nxt].parent = cur;

que.push(sn[nxt]);

}

Kruskal算法

［这个实现等待填坑］

Borůvka算法

［这个实现等待填坑］

有向图最小生成树（最小树形图）

复杂度O(V * E)，以下代码仅存储边，而且会对存储结构发生破坏，请注意。实现来源于国立台湾师范大学。我对这份代码进行了更加详细的注释。

适用于固定了生成树的根的情形

#pragma mark - Chu-Liu-Edmonds Algorithm for Minimum Arborescence (MST on Directed Graph) (MA_CLE)
//注意：会破坏给出的图，可能需要备份
//最小树形图
int V, E;
struct Edge {int a, b, c;} edge[40000];
int d[1000], p[1000], v[1000], n[1000], m[1000];
// 每個點最小入邊的權重，每個點最小入邊的來源，
// 拜訪過，水母環，已收縮。

int MA_CLE(int r){
    memset(m, 0, sizeof(m));
    // 目前生成樹的權重，累計收縮水母環而失去的權重。
    int w1 = 0, w2 = 0;
    while (true) {    // 一旦形成生成樹就停止。最多執行V-1次{
        /* O(E) graph traversal.
         find minimum in-edge for each vertice.

         --->o
         */
        memset(d, 1, sizeof(d));
        memset(p, -1, sizeof(p));

        for (int i=0; i<E; ++i) {
            //iterate every edges
            int& a = edge[i].a;
            int& b = edge[i].b;
            int& c = edge[i].c;
            if (a != b && b != r && c < d[b])
                d[b] = c, p[b] = a;//对于每一个节点，找到指向它的边中最短的那一条（我们要的是“最小”树形图）
        }

        /* O(V) jellyfish detection
         ___
         /   \
         \___/
         _/|||\_
         //1\\
         */
        memset(v, -1, sizeof(v));
        memset(n, -1, sizeof(n));
        w1 = 0;//重置上一次已集计的边权总和
        bool jf = false;//用来标记是不是发现了“水母”
        for (int i=0; i<V; ++i) {
            //iterate every point
            if (m[i]) {
                continue;
                //这种情况下表明这个点已经被缩入某个代表着“水母”的节点了
            }
            if (p[i] == -1 && i != r) {
                return 1e9;
                //这种情况表明当前点并没有任何可用的入边，而且这个点还不是根部，那就表明最小树形图已经没解了，别玩了
            }
            if (p[i] >= 0) {
                w1 += d[i];
                //这里用来集计所有的最短入边，如果这是最后一次的while循环，这时加入w1的边都会被选中作为答案
            }

            // 找水母環
            int s;
            for (s = i; s != -1 && v[s] == -1; s = p[s]){
                v[s] = i;//沿着当前点不断逆着箭头走，如果有环的话，这样最后一定会走回到环的接点停下，如果没环的话，一定会走到路径的端末停下，我们这么走一遭，把走过的都标记上，就得到一只“水母”（“水母”不一定是水母形状）
            }

            // 標記水母環上的點，以及將會被收縮掉的點。
            if (s != -1 && v[s] == i) {
                //这时候的s是这次找出的环的接点，但不是路径的端末。我们要收缩的是由从当前回的i号点发动的找环中找出的的环
                jf = true;//标记上已经找到“水母”
                int j = s;//copy for loop
                do {
                    n[j] = s; //标记属于哪个水母环
                    m[j] = 1;//标记当前点已经被收缩了
                    w2 += d[j];//集计当前水母环的边权（边将会加入w2，并一直保持选中到最后）
                    j = p[j];//沿着路径推进
                } while (j != s);//直到回到了环的接点
                m[s] = 0;//收缩环操作的起点，我们把他当成环的代表点，所以要取消收缩
            }
        }
        if (!jf) break;//没找到水母环的话，后面的事情可以免了

        /* O(E) edge reweighting and cycle contraction
         ___
         /   \ <-
         \___/
         */
        for (int i=0; i<E; ++i) {
            int& a = edge[i].a;
            int& b = edge[i].b;
            int& c = edge[i].c;
            if (n[b] >= 0){
                c -= d[b];
                //删掉已经被收缩的边的边权,注意不是清零，要领会“缩入”这一动作
            }
            if (n[a] >= 0) {
                a = n[a];
                //重定向边的端点至已经缩为一点的水母环
            }
            if (n[b] >= 0) {
                b = n[b];
                //同上
            }
            if (a == b) {
                edge[i--] = edge[--E];
                //如果当前边成了自环，这条边就可以不要了
            }
        }
    }
    return w1 + w2;
    //结算：所有加入w2和w1的边，都是选中的边，要想输出步骤，在这里要加以纪录。
}
#pragma mark -

100

101

102

103

104

105

106

107

108

109

110

#pragma mark - Chu-Liu-Edmonds Algorithm for Minimum Arborescence (MST on Directed Graph) (MA_CLE)

//注意：会破坏给出的图，可能需要备份

//最小树形图

int V, E;

struct Edge {int a, b, c;} edge[40000];

int d[1000], p[1000], v[1000], n[1000], m[1000];

// 每個點最小入邊的權重，每個點最小入邊的來源，

// 拜訪過，水母環，已收縮。

int MA_CLE(int r){

memset(m, 0, sizeof(m));

// 目前生成樹的權重，累計收縮水母環而失去的權重。

int w1 = 0, w2 = 0;

while (true) { // 一旦形成生成樹就停止。最多執行V-1次{

/* O(E) graph traversal.

find minimum in-edge for each vertice.

--->o

memset(d, 1, sizeof(d));

memset(p, -1, sizeof(p));

for (int i=0; i<E; ++i) {

//iterate every edges

int& a = edge[i].a;

int& b = edge[i].b;

int& c = edge[i].c;

if (a != b && b != r && c < d[b])

d[b] = c, p[b] = a;//对于每一个节点，找到指向它的边中最短的那一条（我们要的是“最小”树形图）

}

/* O(V) jellyfish detection

___

/ \

\___/

_/|||\_

//1\\

memset(v, -1, sizeof(v));

memset(n, -1, sizeof(n));

w1 = 0;//重置上一次已集计的边权总和

bool jf = false;//用来标记是不是发现了“水母”

for (int i=0; i<V; ++i) {

//iterate every point

if (m[i]) {

continue;

//这种情况下表明这个点已经被缩入某个代表着“水母”的节点了

}

if (p[i] == -1 && i != r) {

return 1e9;

//这种情况表明当前点并没有任何可用的入边，而且这个点还不是根部，那就表明最小树形图已经没解了，别玩了

}

if (p[i] >= 0) {

w1 += d[i];

//这里用来集计所有的最短入边，如果这是最后一次的while循环，这时加入w1的边都会被选中作为答案

}

// 找水母環

int s;

for (s = i; s != -1 && v[s] == -1; s = p[s]){

v[s] = i;//沿着当前点不断逆着箭头走，如果有环的话，这样最后一定会走回到环的接点停下，如果没环的话，一定会走到路径的端末停下，我们这么走一遭，把走过的都标记上，就得到一只“水母”（“水母”不一定是水母形状）

}

// 標記水母環上的點，以及將會被收縮掉的點。

if (s != -1 && v[s] == i) {

//这时候的s是这次找出的环的接点，但不是路径的端末。我们要收缩的是由从当前回的i号点发动的找环中找出的的环

jf = true;//标记上已经找到“水母”

int j = s;//copy for loop

do {

n[j] = s; //标记属于哪个水母环

m[j] = 1;//标记当前点已经被收缩了

w2 += d[j];//集计当前水母环的边权（边将会加入w2，并一直保持选中到最后）

j = p[j];//沿着路径推进

} while (j != s);//直到回到了环的接点

m[s] = 0;//收缩环操作的起点，我们把他当成环的代表点，所以要取消收缩

}

if (!jf) break;//没找到水母环的话，后面的事情可以免了

/* O(E) edge reweighting and cycle contraction

___

/ \ <-

\___/

for (int i=0; i<E; ++i) {

int& a = edge[i].a;

int& b = edge[i].b;

int& c = edge[i].c;

if (n[b] >= 0){

c -= d[b];

//删掉已经被收缩的边的边权,注意不是清零，要领会“缩入”这一动作

}

if (n[a] >= 0) {

a = n[a];

//重定向边的端点至已经缩为一点的水母环

}

if (n[b] >= 0) {

b = n[b];

//同上

}

if (a == b) {

edge[i--] = edge[--E];

//如果当前边成了自环，这条边就可以不要了

}

return w1 + w2;

//结算：所有加入w2和w1的边，都是选中的边，要想输出步骤，在这里要加以纪录。

}

#pragma mark -

适用于生成树的根无法确定的情形

引用自GentieH，谢谢。

建立虚拟节点x，令x连所有的点，权值为所有边权的总和+1，求得最后结果减去该值即可，由于虚拟节点的存在，不会显式地出现孤立点，这时通过判断如果存在多与1个节点的pre为root，则说明无解。如果需要求出根节点，由于之前将x与图中的点连边时，我们按顺序连的话，考虑到可以用边去标识点，对于每一个终点v，如果它的pre为root，则标记这条边who，在求结果时，让who-E即可。

要求输出方案的情形

CF240E

#pragma mark - Chu-Liu-Edmonds Algorithm for Minimum Arborescence (MST on Directed Graph) (MA_CLE)
//注意：会破坏给出的图，可能需要备份
//最小树形图
const int MAXN = 100005,MAXE = 200005;
int V, E;
struct Edge {int a, b;int c;int id;} edge[MAXE],orig_edge[MAXE];
int d[MAXN],dd[MAXN];
int  p[MAXN], v[MAXN], n[MAXN], m[MAXN];
// 每個點最小入邊的權重，每個點最小入邊的來源，
// 拜訪過，水母環，已收縮。
int used[MAXE*10];
int alter[MAXE*10][2];
int id[MAXN],pos[MAXN];

int MA_CLE(int root)
{
    int nall=E,ans=0;
    while(true)
    {
        fill(d, d+MAXN, 1 << 30);
        memset(pos,-1,sizeof(pos));
        memset(id,-1,sizeof(pos));

        for (int i = 0; i < E; i++) {
            if (edge[i].a != edge[i].b && d[edge[i].b] > edge[i].c) {
                d[edge[i].b] = edge[i].c;
                p[edge[i].b] = edge[i].a;
                dd[edge[i].b] = edge[i].id;
            }
        }
        d[root]=0;
        int nCircle=-1;

        for (int i = 0; i < V; i++) {
            if (d[i] == 1 << 30) {
                return -1;
            }
            if (i != root) {
                used[dd[i]]++;
            }
            int v;
            ans += d[i];
            for (v = i; v != root && pos[v] == -1; v = p[v]) {
                pos[v] = i;
            }
            if (v != root && id[v] == -1 && pos[v] == i) {
                id[v] = ++nCircle;
                for (int j = p[v]; j != v; j = p[j]) {
                    id[j] = nCircle;
                }
            }
        }
        if (nCircle == -1) {
            break;
        }
        for (int i = 0; i < V; i++) {
            if (id[i] == -1) {
                id[i] = ++nCircle;
            }
        }
        for (int i = 0; i < E;i++) {
            int &a = edge[i].a;
            int &b = edge[i].b;
            int &c = edge[i].c;
            int pre = dd[b];
            c -= d[b];
            a = id[a],b = id[b];
            if (a != b) {
                alter[nall][0] = edge[i].id;
                alter[nall][1] = pre;
                edge[i].id = nall++;
            }
        }
        V=nCircle+1,root=id[root];
    }
    for (int i = nall-1; i >= E; i--) {
        if (used[i]) {
            used[alter[i][0]]++;
            used[alter[i][1]]--;
        }
    }
    return ans;
}
#pragma mark -

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int n,m;
    scanf(" %d %d",&n,&m);
    V = n,E = 0;
    int sumc = 0;
    for (int i = 1; i <= m; i++) {
        int a,b,c;
        scanf(" %d %d %d",&a,&b,&c);
        edge[E].a = a-1;
        edge[E].b = b-1;
        edge[E].c = c;
        edge[E].id = E;
        sumc += c;
        E++;
    }
    memcpy(orig_edge, edge, sizeof(edge));
    int res = MA_CLE(0);
    if (res == -1) {
        puts("-1");
    }else{
        printf("%d\n",res);
        if (res) {
            for (int i = 0; i < m; i++) {
                if (used[i] && orig_edge[i].c == 1) {
                    printf("%d ",i+1);
                }
            }
            printf("\n");
        }
    }


}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

#pragma mark - Chu-Liu-Edmonds Algorithm for Minimum Arborescence (MST on Directed Graph) (MA_CLE)

//注意：会破坏给出的图，可能需要备份

//最小树形图

const int MAXN = 100005,MAXE = 200005;

int V, E;

struct Edge {int a, b;int c;int id;} edge[MAXE],orig_edge[MAXE];

int d[MAXN],dd[MAXN];

int p[MAXN], v[MAXN], n[MAXN], m[MAXN];

// 每個點最小入邊的權重，每個點最小入邊的來源，

// 拜訪過，水母環，已收縮。

int used[MAXE*10];

int alter[MAXE*10][2];

int id[MAXN],pos[MAXN];

int MA_CLE(int root)

{

int nall=E,ans=0;

while(true)

{

fill(d, d+MAXN, 1 << 30);

memset(pos,-1,sizeof(pos));

memset(id,-1,sizeof(pos));

for (int i = 0; i < E; i++) {

if (edge[i].a != edge[i].b && d[edge[i].b] > edge[i].c) {

d[edge[i].b] = edge[i].c;

p[edge[i].b] = edge[i].a;

dd[edge[i].b] = edge[i].id;

}

d[root]=0;

int nCircle=-1;

for (int i = 0; i < V; i++) {

if (d[i] == 1 << 30) {

return -1;

}

if (i != root) {

used[dd[i]]++;

}

int v;

ans += d[i];

for (v = i; v != root && pos[v] == -1; v = p[v]) {

pos[v] = i;

}

if (v != root && id[v] == -1 && pos[v] == i) {

id[v] = ++nCircle;

for (int j = p[v]; j != v; j = p[j]) {

id[j] = nCircle;

}

if (nCircle == -1) {

break;

}

for (int i = 0; i < V; i++) {

if (id[i] == -1) {

id[i] = ++nCircle;

}

for (int i = 0; i < E;i++) {

int &a = edge[i].a;

int &b = edge[i].b;

int &c = edge[i].c;

int pre = dd[b];

c -= d[b];

a = id[a],b = id[b];

if (a != b) {

alter[nall][0] = edge[i].id;

alter[nall][1] = pre;

edge[i].id = nall++;

}

V=nCircle+1,root=id[root];

}

for (int i = nall-1; i >= E; i--) {

if (used[i]) {

used[alter[i][0]]++;

used[alter[i][1]]--;

}

return ans;

}

#pragma mark -

int main(){

freopen("input.txt","r",stdin);

freopen("output.txt","w",stdout);

int n,m;

scanf(" %d %d",&n,&m);

V = n,E = 0;

int sumc = 0;

for (int i = 1; i <= m; i++) {

int a,b,c;

scanf(" %d %d %d",&a,&b,&c);

edge[E].a = a-1;

edge[E].b = b-1;

edge[E].c = c;

edge[E].id = E;

sumc += c;

E++;

}

memcpy(orig_edge, edge, sizeof(edge));

int res = MA_CLE(0);

if (res == -1) {

puts("-1");

}else{

printf("%d\n",res);

if (res) {

for (int i = 0; i < m; i++) {

if (used[i] && orig_edge[i].c == 1) {

printf("%d ",i+1);

}

printf("\n");

}

次小生成树

[Pending Session]

增量最小生成树

[Pending Session]

最小瓶颈生成树

[Pending Session]

生成树问题混杂其他类型问题

小技巧实现istream的非空格符分割

May 21, 20152015-05-21hahaschoolLeave a comment

只是个小技巧，然而我现在并不能完全理解这个实现的原理，还是很弱的。

大概是自定义locale，重新定义空白符，再将自定义locale导入istream改变istream的行为。无论是cin还是ifstream都是可以用的。注意imbue完locale之后cin的全局特性都会改变,如果想要恢复原来的istream的行为的话要imbue原来的locale.

#include <iostream>

using namespace std;

class delimiter : public std::ctype<char>
{
public:

    delimiter( const std::string& characters )
    : std::ctype<char>( creatTable( characters ), false ){ }

private:

    std::ctype_base::mask const* creatTable( const std::string& characters )
    {
        std::ctype_base::mask* table = new std::ctype_base::mask[ std::ctype<char>::table_size ];
        std::fill_n( table, std::ctype<char>::table_size, std::ctype_base::mask( ) );
        for( std::string::size_type i = 0; i < characters.size( ); ++i )
        {
            table[ characters[ i ] ] = std::ctype_base::space;
        }
        return table;
    }
};
int main(){
    delimiter delimiters( " ,-" );//usage:add desired delimitors here
    std::cin.imbue( std::locale( std::locale( ), &delimiters ) );//apply customize locale
    /*TEST CASE ONLY
    int a;
    while (cin >> a) {
        cerr << a << endl;
    }*/
    return 0;
}

#include <iostream>

using namespace std;

class delimiter : public std::ctype<char>

{

public:

delimiter( const std::string& characters )

: std::ctype<char>( creatTable( characters ), false ){ }

private:

std::ctype_base::mask const* creatTable( const std::string& characters )

{

std::ctype_base::mask* table = new std::ctype_base::mask[ std::ctype<char>::table_size ];

std::fill_n( table, std::ctype<char>::table_size, std::ctype_base::mask( ) );

for( std::string::size_type i = 0; i < characters.size( ); ++i )

{

table[ characters[ i ] ] = std::ctype_base::space;

}

return table;

}

};

int main(){

delimiter delimiters( " ,-" );//usage:add desired delimitors here

std::cin.imbue( std::locale( std::locale( ), &delimiters ) );//apply customize locale

/*TEST CASE ONLY

int a;

while (cin >> a) {

cerr << a << endl;

}*/

return 0;

}

istream.get()修改delimiter

直接使用get()的第三個參數就可以了，cin.get(目標串, 目標輸入最大長度,分隔符);

但是只能用一個分隔符。

一份仅用于学习的伸展树C实现

April 24, 20152015-04-24hahaschoolLeave a comment

这份代码来自于以前的Wikipedia，遇到这份代码也许是缘分吧，虽然实现上十分的冗长（好多好多的废话），但是也正因为如此这份代码展示了伸展树操作的每一个细节，尽管没什么实用价值，但是拿来理解splay是很好的。我自己抄了一遍同时加上了注释。

//
//  SplayTree.cpp
//  playground
//
//  Created by Adam Chang on 2015/4/11.
//  Copyright (c) 2015年 Adam Chang. All rights reserved.
//

//C Implementation in reference of http://en.wikipedia.org/w/index.php?title=Splay_tree&oldid=533723000
//NON-Recursive Elementary

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

struct node{
    int data;
    node *left;
    node *right;
    node *parent;
};

struct node *rotate_left(struct node *pivot,struct node *root){
    struct node *x;
    x = pivot->right;
    //reassign x's left child to pivot's right child slot
    pivot->right = x->left;
    if (x->left != NULL) {
        x->left->parent = pivot;
    }
    //reverse the parential relation between x and pivot
    x->left = pivot;
    if (pivot->parent != NULL) {
        if (pivot == pivot->parent->left) {
            pivot->parent->left = x;
        }else{
            pivot->parent->right = x;
        }
    }
    x->parent = pivot->parent;
    pivot->parent = x;
    //return value for the splay func to change the tree root
    if (pivot == root) {
        //pivot is the original root,after rotate x become the new root
        return x;
    }else{
        return root;
    }
}

struct node *rotate_right(struct node *pivot,struct node *root){
    //x is pivot's left child
    struct node *x;
    x = pivot->left;
    //assign x's right child to pivot's left child slot
    pivot->left = x -> right;
    if (x->right != NULL) {
        x->right->parent = pivot;
    }
    //reverse the parental relationship between x and pivot
    x->right = pivot;
    if (pivot->parent != NULL) {
        if (pivot == pivot->parent->right) {
            pivot->parent->right = x;
        }else {
            pivot->parent->left = x;
        }
    }
    x->parent = pivot->parent;
    pivot->parent = x;
    //the return value is for the splay func to change the tree root
    if (pivot == root) {
        //pivot is the original root,after rotate x become the new root
        return x;
    }else{
        return root;
    }
}

void splay(struct node *x,struct node *root){
    //x is root,no operation required
    if (x == root) {
        return;
    }else if(x->parent == root){
        //single rotation required
        if (x == x->parent->left) {
            //x on the root's left,let root be the pivot and throw the x onto the root pos
            root = rotate_right(root, root);
        }else{
            //conversely
            root = rotate_left(root, root);
        }
    }else {
        //complex situation,multiple rotation required
        node *p,*g;//p:parent node g:grandparent node
        p = x->parent;
        g = p->parent;
        if (x == p->left && p == g->left) {
            //double right rotation
            root = rotate_right(g, root);
            root = rotate_right(p, root);
        }else if(x == p->right && p == g->right){
            //double left rotation
            root = rotate_left(g, root);
            root = rotate_left(p, root);
        }else if(x == p->left && p == g->right){
            //perform right-left(zagzig) rotation
            root = rotate_right(p, root);
            root = rotate_left(g, root);
        }else if(x == p->right && p == g->left){
            //perform left-right(zigzag) rotation
            root = rotate_left(p, root);
            root = rotate_right(g, root);
        }
        //when in complex situation,the splay cannot terminate only after once,use recursion here.
        splay(x, root);
    }
}

struct node *insert(struct node *root,int value){
    struct node *temp1,*temp2,*par;
    if (root == NULL) {
        //given subtree root doesn't exist,create one and return this new subroot for splay.
        root = (struct node *)malloc(sizeof(struct node));
        if (root != NULL) {
            root->data = value;
            root->parent = NULL;
            root->left = NULL;
            root->right = NULL;
        }else{
            //handle memory exception
            printf("MEMORY ALLOCATION EXCEPTION\n");
            exit(0);
        }
    }else{
        temp2 = root;
        while (temp2 != NULL) {
            //iteriate until we find a good place to place the new node
            temp1 = temp2;//save current node as the target node(or its place)'s parent
            if (temp2->data > value) {
                temp2 = temp2->left;
            }else if(temp2->data < value){
                temp2 = temp2->right;
            }else{
                //temp2->data==value no need to instert,just return this node
                //(we don't accept nodes with same key),in this case insert becomes search
                return temp2;
            }
        }
        if (temp1->data > value) {
            par = temp1;//par is now the target's parent
            temp1->left = (struct node *)malloc(sizeof(struct node));
            temp1 = temp1->left;//temp1 is now the target node
            if (temp1 != NULL) {
                temp1->data = value;
                temp1->parent = par;
                temp1->left = NULL;
                temp1->right = NULL;
            }else{
                //handle memory exception
                printf("MEMORY ALLOCATION EXCEPTION\n");
                exit(0);
            }
        }else{
            //only repeating itself(REFACTORIZATION REQUIRED)
            par = temp1;//par is now the target's parent
            temp1->right = (struct node *)malloc(sizeof(struct node));
            temp1 = temp1->right;//temp1 is now the target node
            if (temp1 != NULL) {
                temp1->data = value;
                temp1->parent = par;
                temp1->left = NULL;
                temp1->right = NULL;
            }else{
                //handle memory exception
                printf("MEMORY ALLOCATION EXCEPTION\n");
                exit(0);
            }
        }
    }
    splay(temp1, root);//splay the newly inserted node to root position
    return temp1;//this func. returns the pointer of newly inserted node for futher ops.
}

struct node *lookup(struct node *root,int value){
    struct node *temp1,*temp2;
    if (root != NULL) {
        temp1 = root;//temp2 is the target pos for return,temp1 is only for iteration
        temp2 = temp1;
        while (temp1 != NULL) {
            temp2 = temp1;
            if (temp1->data > value) {
                temp1 = temp1->left;
            }else if(temp1->data < value){
                temp1 = temp1->right;
            }else{
                return temp1;//already found,just return it.
            }
        }
        return temp2;//didn't find the node but we find it's parent(assuming the node exists),return the parent;
    }else{
        printf("ROOT NULL EXCEPTION\n");
        exit(0);
    }
}

struct node *successor(struct node *x){
    //get the assuming node's right subtree's leftmost child
    struct node *temp1,*temp2;
    temp1 = temp2 = x->right;
    while (temp1 != NULL) {
        temp2 = temp1;
        temp1 = temp1->left;
    }
    return temp2;
}

struct node *remove(struct node *root,int value){
    struct node *x,*y,*s;//y is the new root after removal
    x = lookup(root, value);
    if (x->data == value) {
        //we have located the node matched for remove
        if (x->left == NULL && x->right == NULL) {
            if (x == root) {
                //special judge to avoid root fault
                y = root = NULL;//if root is leaf,simply make NULL the new root
            }else{
                //if the node for remove is a leaf
                y = x->parent;
                if (x == (y->right)) {
                    y->right = NULL;
                }else{
                    y->left = NULL;
                }//unlink x from its parent
            }
        }else if(x->left != NULL && x->right == NULL){
            if (x == root) {//root fault prevention
                x->left->parent = NULL;//x's lch becomes the new root
                y = x->left;
                root = x->left;
            }else{
                //if the node for removal only have left child
                y = x->parent;
                if (x == y->left) {
                    x->left->parent = y;//relink the child
                    y->left = x->left;
                }else{
                    x->left->parent = y;//relink
                    y->right = x->left;
                }
            }
        }else if(x->left == NULL && x->right != NULL){
            if(x == root) {
                //avoid root fault
                x->right->parent=NULL;//x's rch becomes the new root
                y=x->right;
                root=x->right;
            }
            else {
                //if the node to remove only have right child
                y = x->parent;
                //we just repeat ourself as above...
                if (x == y->left) {
                    x->right->parent = y;
                    y->left = x->right;
                }else{
                    x->right->parent = y;
                    y->right = x->right;
                }
            }
        }else{
            //if the node for removal have both childs
            if (x == root) {
                s = successor(x);//find successor(rch's leftmost node)
                if (s == x->right) {
                    //if successor is right at x's rch
                    y = s;
                    s->parent = NULL;//make s the new root,relink x's lch
                    x->left->parent = s;
                    s->left = x->left;
                    root = s;
                }else{
                    y = s->parent;//s's parent should be the new root after splay
                    if (s->right != NULL) {
                        s->right->parent = y;//relink s's rch to s's parent(because s goes to root)
                        y->left = s->right;
                    }else{
                        y->left = NULL;//unlink s's parent's lch
                    }
                    s->parent = NULL;//s is now the new root
                    x->right->parent = s;//relink
                    x->left->parent = s;
                    s->right = x->right;
                    s->left = x->left;
                    root = s;
                }
            }else{
                y = x->parent;
                if (x == y->left) {
                    s = successor(x); //find x's right's leftmost to replace x
                    if (s != x->right) {
                        y = s->parent;
                        if (s->right != NULL) {
                            //if the successor have right child
                            s->right->parent = y;//relink its right child to x's parent(s goes to x's parent's left)
                            y->left = s->right;
                        }else{
                            y->left = NULL;
                        }
                        s->parent = s->parent;//the relink proccess can be better understood by illustration
                        x->right->parent = s;
                        x->left->parent = s;
                        s->right = x->right;
                        s->left = x->left;
                        x->parent->left = s;
                    }else{
                        y = s;
                        s->parent = x->parent;
                        x->left->parent = s;
                        s->left = x->left;
                        x->parent->left = s;
                    }
                }else{
                    s = successor(x);//we are repeating
                    if (s != x->right) {
                        y = s->parent;
                        if (s->right != NULL) {
                            s->right->parent = y;
                            y->left = s->right;
                        }else{
                            y->left = NULL;
                        }
                        s->parent = x->parent;
                        s->right->parent = s;
                        x->left->parent = s;
                        s->right = x->right;
                        s->left = x->left;
                        x->parent->right = s;
                    }else{
                        y = s;
                        s->parent = x->parent;
                        s->left->parent = s;
                        s->left = x->left;
                        x->parent->right = s;
                    }
                }
            }
        }
        free(x);//destroy and free
        splay(y, root);//splay y to the new root's position
        return y;
    }else{
        splay(x, root);//found nothing to delete,but still we should splay
        return x;
    }
}


int main(){

    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

// SplayTree.cpp

// playground

// Created by Adam Chang on 2015/4/11.

//C Implementation in reference of http://en.wikipedia.org/w/index.php?title=Splay_tree&oldid=533723000

//NON-Recursive Elementary

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

struct node{

int data;

node *left;

node *right;

node *parent;

};

struct node *rotate_left(struct node *pivot,struct node *root){

struct node *x;

x = pivot->right;

//reassign x's left child to pivot's right child slot

pivot->right = x->left;

if (x->left != NULL) {

x->left->parent = pivot;

}

//reverse the parential relation between x and pivot

x->left = pivot;

if (pivot->parent != NULL) {

if (pivot == pivot->parent->left) {

pivot->parent->left = x;

}else{

pivot->parent->right = x;

}

x->parent = pivot->parent;

pivot->parent = x;

//return value for the splay func to change the tree root

if (pivot == root) {

//pivot is the original root,after rotate x become the new root

return x;

}else{

return root;

}

struct node *rotate_right(struct node *pivot,struct node *root){

//x is pivot's left child

struct node *x;

x = pivot->left;

//assign x's right child to pivot's left child slot

pivot->left = x -> right;

if (x->right != NULL) {

x->right->parent = pivot;

}

//reverse the parental relationship between x and pivot

x->right = pivot;

if (pivot->parent != NULL) {

if (pivot == pivot->parent->right) {

pivot->parent->right = x;

}else {

pivot->parent->left = x;

}

x->parent = pivot->parent;

pivot->parent = x;

//the return value is for the splay func to change the tree root

if (pivot == root) {

//pivot is the original root,after rotate x become the new root

return x;

}else{

return root;

}

void splay(struct node *x,struct node *root){

//x is root,no operation required

if (x == root) {

return;

}else if(x->parent == root){

//single rotation required

if (x == x->parent->left) {

//x on the root's left,let root be the pivot and throw the x onto the root pos

root = rotate_right(root, root);

}else{

//conversely

root = rotate_left(root, root);

}

}else {

//complex situation,multiple rotation required

node *p,*g;//p:parent node g:grandparent node

p = x->parent;

g = p->parent;

if (x == p->left && p == g->left) {

//double right rotation

root = rotate_right(g, root);

root = rotate_right(p, root);

}else if(x == p->right && p == g->right){

//double left rotation

root = rotate_left(g, root);

root = rotate_left(p, root);

}else if(x == p->left && p == g->right){

//perform right-left(zagzig) rotation

root = rotate_right(p, root);

root = rotate_left(g, root);

}else if(x == p->right && p == g->left){

//perform left-right(zigzag) rotation

root = rotate_left(p, root);

root = rotate_right(g, root);

}

//when in complex situation,the splay cannot terminate only after once,use recursion here.

splay(x, root);

}

struct node *insert(struct node *root,int value){

struct node *temp1,*temp2,*par;

if (root == NULL) {

//given subtree root doesn't exist,create one and return this new subroot for splay.

root = (struct node *)malloc(sizeof(struct node));

if (root != NULL) {

root->data = value;

root->parent = NULL;

root->left = NULL;

root->right = NULL;

}else{

//handle memory exception

printf("MEMORY ALLOCATION EXCEPTION\n");

exit(0);

}

}else{

temp2 = root;

while (temp2 != NULL) {

//iteriate until we find a good place to place the new node

temp1 = temp2;//save current node as the target node(or its place)'s parent

if (temp2->data > value) {

temp2 = temp2->left;

}else if(temp2->data < value){

temp2 = temp2->right;

}else{

//temp2->data==value no need to instert,just return this node

//(we don't accept nodes with same key),in this case insert becomes search

return temp2;

}

if (temp1->data > value) {

par = temp1;//par is now the target's parent

temp1->left = (struct node *)malloc(sizeof(struct node));

temp1 = temp1->left;//temp1 is now the target node

if (temp1 != NULL) {

temp1->data = value;

temp1->parent = par;

temp1->left = NULL;

temp1->right = NULL;

}else{

//handle memory exception

printf("MEMORY ALLOCATION EXCEPTION\n");

exit(0);

}

}else{

//only repeating itself(REFACTORIZATION REQUIRED)

par = temp1;//par is now the target's parent

temp1->right = (struct node *)malloc(sizeof(struct node));

temp1 = temp1->right;//temp1 is now the target node

if (temp1 != NULL) {

temp1->data = value;

temp1->parent = par;

temp1->left = NULL;

temp1->right = NULL;

}else{

//handle memory exception

printf("MEMORY ALLOCATION EXCEPTION\n");

exit(0);

}

splay(temp1, root);//splay the newly inserted node to root position

return temp1;//this func. returns the pointer of newly inserted node for futher ops.

}

struct node *lookup(struct node *root,int value){

struct node *temp1,*temp2;

if (root != NULL) {

temp1 = root;//temp2 is the target pos for return,temp1 is only for iteration

temp2 = temp1;

while (temp1 != NULL) {

temp2 = temp1;

if (temp1->data > value) {

temp1 = temp1->left;

}else if(temp1->data < value){

temp1 = temp1->right;

}else{

return temp1;//already found,just return it.

}

return temp2;//didn't find the node but we find it's parent(assuming the node exists),return the parent;

}else{

printf("ROOT NULL EXCEPTION\n");

exit(0);

}

struct node *successor(struct node *x){

//get the assuming node's right subtree's leftmost child

struct node *temp1,*temp2;

temp1 = temp2 = x->right;

while (temp1 != NULL) {

temp2 = temp1;

temp1 = temp1->left;

}

return temp2;

}

struct node *remove(struct node *root,int value){

struct node *x,*y,*s;//y is the new root after removal

x = lookup(root, value);

if (x->data == value) {

//we have located the node matched for remove

if (x->left == NULL && x->right == NULL) {

if (x == root) {

//special judge to avoid root fault

y = root = NULL;//if root is leaf,simply make NULL the new root

}else{

//if the node for remove is a leaf

y = x->parent;

if (x == (y->right)) {

y->right = NULL;

}else{

y->left = NULL;

}//unlink x from its parent

}

}else if(x->left != NULL && x->right == NULL){

if (x == root) {//root fault prevention

x->left->parent = NULL;//x's lch becomes the new root

y = x->left;

root = x->left;

}else{

//if the node for removal only have left child

y = x->parent;

if (x == y->left) {

x->left->parent = y;//relink the child

y->left = x->left;

}else{

x->left->parent = y;//relink

y->right = x->left;

}

}else if(x->left == NULL && x->right != NULL){

if(x == root) {

//avoid root fault

x->right->parent=NULL;//x's rch becomes the new root

y=x->right;

root=x->right;

}

else {

//if the node to remove only have right child

y = x->parent;

//we just repeat ourself as above...

if (x == y->left) {

x->right->parent = y;

y->left = x->right;

}else{

x->right->parent = y;

y->right = x->right;

}

}else{

//if the node for removal have both childs

if (x == root) {

s = successor(x);//find successor(rch's leftmost node)

if (s == x->right) {

//if successor is right at x's rch

y = s;

s->parent = NULL;//make s the new root,relink x's lch

x->left->parent = s;

s->left = x->left;

root = s;

}else{

y = s->parent;//s's parent should be the new root after splay

if (s->right != NULL) {

s->right->parent = y;//relink s's rch to s's parent(because s goes to root)

y->left = s->right;

}else{

y->left = NULL;//unlink s's parent's lch

}

s->parent = NULL;//s is now the new root

x->right->parent = s;//relink

x->left->parent = s;

s->right = x->right;

s->left = x->left;

root = s;

}

}else{

y = x->parent;

if (x == y->left) {

s = successor(x); //find x's right's leftmost to replace x

if (s != x->right) {

y = s->parent;

if (s->right != NULL) {

//if the successor have right child

s->right->parent = y;//relink its right child to x's parent(s goes to x's parent's left)

y->left = s->right;

}else{

y->left = NULL;

}

s->parent = s->parent;//the relink proccess can be better understood by illustration

x->right->parent = s;

x->left->parent = s;

s->right = x->right;

s->left = x->left;

x->parent->left = s;

}else{

y = s;

s->parent = x->parent;

x->left->parent = s;

s->left = x->left;

x->parent->left = s;

}

}else{

s = successor(x);//we are repeating

if (s != x->right) {

y = s->parent;

if (s->right != NULL) {

s->right->parent = y;

y->left = s->right;

}else{

y->left = NULL;

}

s->parent = x->parent;

s->right->parent = s;

x->left->parent = s;

s->right = x->right;

s->left = x->left;

x->parent->right = s;

}else{

y = s;

s->parent = x->parent;

s->left->parent = s;

s->left = x->left;

x->parent->right = s;

}

free(x);//destroy and free

splay(y, root);//splay y to the new root's position

return y;

}else{

splay(x, root);//found nothing to delete,but still we should splay

return x;

}

int main(){

return 0;

}

关于欧拉回路和欧拉路径

April 07, 20152015-04-07hahaschoolOne Comment

请留意本文转载自http://www.cppblog.com/abilitytao/archive/2010/07/26/121319.html

如果侵犯了您（原作者）的权益请联系我删除，谢谢。

定义：
欧拉回路：每条边恰好只走一次，并能回到出发点的路径
欧拉路径：经过每一条边一次，但是不要求回到起始点

①首先看欧拉回路存在性的判定：

一、无向图
每个顶点的度数都是偶数，则存在欧拉回路。

二、有向图（所有边都是单向的）
每个节顶点的入度都等于出度，则存在欧拉回路。

三.混合图欧拉回路
混合图欧拉回路用的是网络流。
把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以2，得x。也就是说，对于每一个点，只要将x条边改变方向（入>出就是变入，出>入就是变出），就能保证出 = 入。如果每个点都是出 = 入，那么很明显，该图就存在欧拉回路。
现在的问题就变成了：我该改变哪些边，可以让每个点出 = 入？构造网络流模型。首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定向了吗？定的是什么向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入 > 出的点u，连接边(u, t)、容量为x，对于出 > 入的点v，连接边(s, v)，容量为x（注意对不同的点x不同）。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。欧拉回路是哪个？查看流值分配，将所有流量非 0（上限是1，流值不是0就是1）的边反向，就能得到每点入度 = 出度的欧拉图。
由于是满流，所以每个入 > 出的点，都有x条边进来，将这些进来的边反向，OK，入 = 出了。对于出 > 入的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是出 > 入，和t连接的条件是入 > 出，那么这个既没和s也没和t连接的点，自然早在开始就已经满足入 = 出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
所以，就这样，混合图欧拉回路问题，解了。
②.欧拉路径存在性的判定

一。无向图
一个无向图存在欧拉路径，当且仅当该图所有顶点的度数为偶数或者除了两个度数为奇数外其余的全是偶数。

二。有向图
一个有向图存在欧拉路径，当且仅当该图所有顶点的度数为零或者一个顶点的度数为1，另一个度数为-1，其他顶点的度数为0。

三。混合图欧拉路径
其实整篇文章只有这部分是我写的哈，灰常不好意思，只是网上的同志们写的太好了，实在没有必要重复劳动，不知道大家有没有发现，求欧拉路径的第一步一定是求欧拉回路，在混合图上也不例外，如何判断混合图欧拉回路问题的存在性呢？首先，我们用上文所说的方法判断该图是否存在欧拉回路，如果存在，欧拉路径一定存在。如果欧拉回路不存在，那么我们枚举欧拉路径的起点和终点，连接一条无向边，然后再用最大流判断是否存在欧拉回路即可。

求有向图强连通分量的Tarjan算法

January 18, 20152015-01-18hahaschoolLeave a comment

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

vector<int> ljb[10005];
bool vis[10005];
bool instk[10005];
int dfn[10005];
int low[10005];
int tim = 0;
stack<int> stk;
vector<vector<int> > ccs;

void dfs(int currNode){
    vis[currNode] = true;
    dfn[currNode] = low[currNode] = tim++;
    stk.push(currNode);
    instk[currNode] = true;
    vector<int> now = ljb[currNode];
    for (int i = 0;i < now.size(); i++) {
        if (!vis[now[i]]) {
            dfs(now[i]);
            low[currNode] = min(low[currNode],low[now[i]]);
        }else if (instk[now[i]]) {
                low[currNode] = min(low[currNode],dfn[now[i]]);
        }
    }
    if (dfn[currNode] == low[currNode]) {
        int tmp = 0;
        vector<int> res;
        while (currNode != tmp) {
            tmp = stk.top();
            res.push_back(tmp);
            //cout << tmp << "~";
            stk.pop();
            instk[tmp] = false;
        }
        //sort(res.begin(),res.end());
        ccs.push_back(res);
        //cout << endl;
    }
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

using namespace std;

vector<int> ljb[10005];

bool vis[10005];

bool instk[10005];

int dfn[10005];

int low[10005];

int tim = 0;

stack<int> stk;

vector<vector<int> > ccs;

void dfs(int currNode){

vis[currNode] = true;

dfn[currNode] = low[currNode] = tim++;

stk.push(currNode);

instk[currNode] = true;

vector<int> now = ljb[currNode];

for (int i = 0;i < now.size(); i++) {

if (!vis[now[i]]) {

dfs(now[i]);

low[currNode] = min(low[currNode],low[now[i]]);

}else if (instk[now[i]]) {

low[currNode] = min(low[currNode],dfn[now[i]]);

}

if (dfn[currNode] == low[currNode]) {

int tmp = 0;

vector<int> res;

while (currNode != tmp) {

tmp = stk.top();

res.push_back(tmp);

//cout << tmp << "~";

stk.pop();

instk[tmp] = false;

}

//sort(res.begin(),res.end());

ccs.push_back(res);

//cout << endl;

}

-_-#上面的ccs应该是scc，名字叫错了跪。。。

关于Tarjan，https://www.byvoid.com/blog/scc-tarjan这个讲的挺好，一定要看看。然后我说下我自己咋想的。

首先初始化，对于每个节点都要分配一个dfn值和low值，开一个tim当作计时器，然后基本的流程就是：

～进入当前节点
～tim＋＋
～当前节点dfn＝low＝tim
～标记当前结点已经走过（注意图的遍历中节点只会走一次，也就是说标记不用撤销）
～把当前节点压入栈中（这个stack预先开好了）
～开始扫当前节点的分支，如果这个分支走过了，判断一下是不是这个分支是不是在栈里，如果在栈里的话就看看分支的dfn是不是比当前节点的low还小，小的话就把当前的low值调成那个dfn值；如果分支没走过，直接递归进到那个分支里去，等到递归出来之后，如果分支的low值比当前low值小，就令当前low值为分支low值（这步比较难懂）
～等到所有分支扫完，检查一下当前的dfn是不是等于low，如果不相等直接退出当前递归就好；相等的话，说明节点是scc的根，这个时候不断弹出栈，直到当前节点也被弹出，弹出的这些节点放在一起就是一组scc。

其实这个Tarjan的原理就是利用时间标记，进入栈的节点都是预定互相连通的，dfu值的意思就是当遍历到这个节点，是第几步（我把tim当作步来看），low的意思就是从当前节点可以走到的尽量在时间上先走到的栈内节点对应的dfu，就是最优解的对应标号，这个low肯定是越小越好，因为low越小我们的连通回路就越大。如果low＝dfu，那就是当前个点已经没有办法和栈里的既有的点连通了，所以当尝试了全部的走法之后还是没有找到一个栈里的节点来和当前点连通，就说明这个连通回路闭合了，这个时候只要把整个连通回路统统从栈里弹出来，就能得到整个连通回路，也就是scc的一个。每步中接下来要走的节点有三种情况：有的节点访问过但是不在栈里，这样的点不用考虑，因为它已经被弹出了，相当于这个节点已经和我们没关系了；有的点访问过而且在栈里，这样的节点有可能就是当前连通回路的终点了，所以我们要比较一下当前low值是不是比它的dfu大，如果大的话说明这个点可以连通过去，如果小的话说明我们已经有一种连通方式可以包括和它连通了，这个不是最优解，我们就忽略好了；有的节点没访问过，这样的点我们要递归进去处理一下，递归完之后这个节点就有了它在当前情形下该有的dfu和low了，因为这个点和当前点连通，所以这个点要是有一个比当前更好的连通方案，我们用它的就好。

基本就是这么搞，这种时间流逝标记的方法很重要（虽然我还不知道到底有多重要。。。）。

Linux权限姿势小总结

January 13, 20152015-01-13hahaschoolLeave a comment

首先是会读权限：

ls -al的时候，会出来10个字符，可以分为四段：

先说一点，linux下啥都是文件

［d］［rwx］［rwx］［rwx］

第一段是类型，d是目录，－是普通文件，当然还有好多别的（设备啦什么的）
第二段是owner权限，如果没有chown过的话，创建这货的人就是owner，owner的权限看这一段
第三段是group权限，如果没有chgrp或者chown过的话，创建这货的人是哪个组的这个文件的group也就对应哪个组，在这个group内，还不是owner的人，要看这个权限
第四段是other权限如果访问这个文件的人既不是owner，也不是这个文件对应group里面的用户，那就是要看这段权限

然后就是每一段的rwx是啥：

r：read，对于普通文件，就是读取文件内容的权利，对于目录，就是查询目录结构的权利。

w：write，对于普通文件，就是改变文件内容的权利，对于目录，就是改变目录结构的权利（我说过了目录是文件，可以把目录当成一张索引表）。

x：execute，这货就比较特殊，对于普通文件来说，凡是打上x权限的文件，都是可执行文件（这个和windows里面依靠文件类型来区分的机制不一样），对于目录来说，打上x权限的意思是可以进去目录（也就是说即使目录权限是r－－，不是r－x，目录也是进不去的，里面的文件不管权限怎么样，也打不开，因为要先进目录再开文件）

rwx是三个基本权限，然后还有附加权限三个：

［－］［－－s］［－－s］［－－t］

有时候会像上面那样本来是x的位置变成s或者t了，这个时候说明文件有特别权限

第一个是setuid，这个权限开启与否会显示在owner权限的第3位，如果owner权限有x，显示为s，没有x，显示为S。这个权限的意思是当文件执行时，强行让执行的那个人适用owner的权限（就是说假如这个文件的权限是-rwsr–r–,本来非owner是不能写和执行的，但是因为开了setuid权限，现在谁都可以有写和执行的权利了，因为他们都被当成了文件的owner，用rwx权限）。

第二个是setgid，这个权限只能给目录开，显示在group权限的第三位，有x为s，没x为S。这个setgid的意思就是在这个目录下创建文件的话，不管是谁创建的，新建的文件的group都会被强行设为这个目录的group

第三个是sticky bit，显示在other权限的第三位，有x为t，没x为T。这个权限就是不让删除的意思，防删标记。有一些-rwxrwxrwx的文件比较重要又怕手滑的话可以开这个权限。
该位可以理解为防删除位. 一个文件是否可以被某用户删除, 主要取决于该文件所属的组是否对该用户具有写权限. 如果没有写权限, 则这个目录下的所有文件都不能被删除, 同时也不能添加新的文件. 如果希望用户能够添加文件但同时不能删除文件, 则可以对文件使用sticky bit位. 设置该位后, 就算用户对目录具有写权限, 也不能删除该文件.

到这里关于权限本身的简单的东西基本都有了，然后就是chmod怎么用的问题：

chmod ［权限］［文件］

这个［权限］的写法有一种比较简单的方式就是数字表示法：

这里把权限分为四组：［特殊］［owner］［group］［other］

对于后三组，如果开r权限，就算4，开w权限，就算2，开x权限，就算1（特殊权限都在第四组开，前三组只负责rwx），其实就是三个二进制位啦，把每一组的权限对应的数字加起来，就是这一组的权限，然后按着顺序把三个组权限都写出来就ok了。
举个例子：rwxr－－rw－，翻译完就是7（4+2+1）4（4）6（4＋2），chmod 0746 ［文件］之后这个文件的权限就是rwxr－－rw－了。

第一组如果开setuid，就算4，开setgid就算2，开sticky bit就算1，相加填到第四位上就行。

注意，后三位一定要都给出，第一位没有需要的话，可以不给出，只给三位的话默认就是没有特殊权限.