图

图的存储：

邻接矩阵
邻接链表
链式前向星 = 边集数组+邻接表

链式前向星代码，维护一个head头数组，以及一个edges[]边数组。
链式前向星可以快速访问一个节点的所有邻近节点，在算法竞赛中广泛使用。链式前向星有两种写法，一种是struct，一种是三个数组head[]、next[]、to[].

/* 链式前向星 */
#include <iostream>
#include <cstring>

using namespace std;

const int maxn=500+5, maxe=100000+1;
int n, m, cnt;
int head[maxn];  // 头节点数组 保存节点

struct node{
    int to, next, w;  // to 表示到达的节点 next表示下一个节点  w表示权重
}edge[maxe];  // 边集数组

void add(int u, int v, int w){  // 添加一条边  头插法  无向图就是输入两遍 add(u, v, w) add(v, u, w)
    edge[cnt].to = v;
    edge[cnt].w =w;
    edge[cnt].next = head[u];
    head[u] = cnt++;  // 给head[u]复制过后，然后在使得cnt++，边计数
}

void printg(){
    for(int u=1; u<n; u++){
        cout << u << " ";
        for(int i=head[u]; i!=-1; i=edge[i].next){  // head[u] 第一条边 判断head[u]不等于-1
            cout << "--->" << i << ":(" << edge[i].to << " " << edge[i].w << " " << edge[i].next << ")";
        }
        cout << endl;
    }
}

int main(){
    freopen("test.txt", "r", stdin);
    cin >> n >> m;  // n：节点数  m：边数
    cnt = 0;  // 边从0来计数
    memset(head, -1, sizeof(head));  // 初始给handj数组赋值为-1，  -1表示没有下一条节点
    int u, v, w;
    for(int i=1; i<=m; i++){  // m条边
        cin >> u >> v >> w;
        // 无向图添加两边
        add(u, v, w); //两条边
        add(v, u, w);
    }
    printg();
    return 0;
}

https://www.luogu.org/problem/P3916

数组控制：

/* 没有定义结构体，定义的是数组 next[maxn], to[maxn] */
#include <iostream>

using namespace std;

const int maxn = 100000+5;
int n, m, x, y, total;
int maxx[maxn], head[maxn], nextn[maxn], to[maxn];
// maxx：记录每个点能够到达的最大点  head：头节点  next：每个节点能够到达的下一个节点   to：能够到达的邻接点

void add(int u, int v){ // 添加一条u---v的边
    nextn[++total] = head[u];  // next从1开始d
    head[u] = total;
    to[total] = v;
}

void dfs(int u, int v){
    if(maxx[u])
        return;
    maxx[u] = v;
    
    // 访问u节点的所有邻接点
    for(register int  e=head[u]; e; e=nextn[e]){
        if(!maxx[to[e]])
            dfs(to[e], v);
    }
    // register修饰符暗示编译程序相应的变量将被频繁地使用，如果可能的话，应将其保存在CPU的寄存器中，以加快其存储速度
}

int main(){
    freopen("test.txt", "r", stdin);
    cin >> n >> m;
    total = 0;
    for(int i=1; i<=m; i++){
        cin >> x >> y;
        add(y, x);   // 添加反向边
    }
    // 从每个节点出发
    for(int i=n; i; i--){  // 倒序深度遍历
        dfs(i, i);
    }
    for(int i=1; i<=n; i++){
        if(i!=1) // 控制输出：第一个数前面没有空格，后面的数前面都有空格
            cout << " ";
        cout << maxx[i];
    }
    return 0;
}

结构体控制：

#include <iostream>
#include <cstring>

using namespace std;

const int maxn = 100000+5;
int n, m, x, y, total;
int maxx[maxn], head[maxn];

struct node{
    int to;
    int next;
}edge[maxn];

void add(int u, int v){
    edge[total].to = v;
    edge[total].next = head[u];
    head[u] = total;
    total++;
}

void printg(){
    for(int u=1; u<=n; u++){
        cout << u << " ";
        for(int i=head[u]; i!=-1; i=edge[i].next){  // head[u] 第一条边 判断head[u]不等于-1
            cout << "--->" << i << ":(" << edge[i].to << " " <<  edge[i].next << ")";
        }
        cout << endl;
    }
}

void dfs(int index, int targ){
    // cout << index << " " << targ << endl;
    if(maxx[index])
        return;
    
    maxx[index] = targ;
    for(int i=head[index]; i!=-1; i=edge[i].next){
        // cout << head[index] << endl;
        // cout << i << endl;
        // cout << edge[i].to << endl;
        if(!maxx[edge[i].to])
            dfs(edge[i].to, targ);
    }
}



int main(){
    freopen("test.txt", "r", stdin);
    cin >> n >> m;
    total = 0;
    memset(head, -1, sizeof(head));
    for(int i=1; i<=m; i++){
        cin >> x >> y;
        add(y, x);
    }
    // printg();
    for(int i=n; i>0; i--){
        dfs(i, i);
    }
    
    for(int i=1; i<=n; i++){
        if(i!=1)
            cout << " ";
        cout << maxx[i];
    }
    return 0;
}

字符串子串树

#include <iostream>
#include <cstring>
#include <string>

using namespace std;
const int maxn= 100+10, maxe=(maxn-1)*maxn/2;
string s;
int n;

struct node{
    int to;  // 到达的节点，该节点
    int next;  // 下一条跳节点
}edge[maxe];

int head[maxn];
int cnt;

void add(int u, int v){  // 从u到v
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
    cnt++;
}

void printg(int k, int n){
    for(int u=k; u<n; u++){
        // cout << u << " " << head[u] << " ";
        cout << u << " ";
        for(int i=head[u]; i!=-1; i=edge[i].next){
            cout << "--->" << i << ":(" << edge[i].to << " " <<  edge[i].next << ")";
        }
        cout << endl;
    }
}

string sub_str;

void dfs(int index){
    // cout << index;
    sub_str += char(index+'a');
    if(head[index] == -1){
        cout << sub_str << endl;
        sub_str = sub_str.substr(0, sub_str.length() - 1);  // 去除最后一个字符
    }
    for(int i=head[index]; i!=-1; i=edge[i].next){
        dfs(edge[i].to);
    }
}

int main(){
    freopen("test.txt", "r", stdin);
    cin >> s;
    n = s.length();
    for(int k=0; k<n; k++){
        // 每个k构建一棵树
        cnt = 0;
        memset(edge, NULL, sizeof(edge));
        memset(head, -1, sizeof(head));
        sub_str = "";
        for(int i=k; i<n; i++){
            for(int j=i+1; j<n; j++){
                // cout << s[i] << " " << s[j] << endl;
                // cout << s[i]-'a' << " " << s[j]-'a' << endl;
                add(s[i]-'a', s[j]-'a');
            }
        }
        printg(k, n);
        // 深度优先遍历
        dfs(k);
        cout << endl;
        
    }
    return 0;
}

判断子串是否回文

#include <iostream>
#include <cstring>
#include <string>

using namespace std;
const int maxn= 100+10, maxe=(maxn-1)*maxn/2;
string s;
int n;

struct node{
    int to;  // 到达的节点，该节点
    int next;  // 下一条跳节点
}edge[maxe];

int head[maxn];
int cnt;

void add(int u, int v){  // 从u到v
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
    cnt++;
}

void printg(int k, int n){
    for(int u=k; u<n; u++){
        // cout << u << " " << head[u] << " ";
        cout << u << " ";
        for(int i=head[u]; i!=-1; i=edge[i].next){
            cout << "--->" << i << ":(" << edge[i].to << " " <<  edge[i].next << ")";
        }
        cout << endl;
    }
}

string sub_str;

bool huiwen(string str){
    for(int i=0; i<str.length()/2; i++){
        if(str[i] != str[str.length()-i-1])
            return false;
    }
    return true;
}

void dfs(int index){
    // cout << index;
    sub_str += char(index+'a');
    if(head[index] == -1){
        // cout << sub_str << endl;
        if(huiwen(sub_str)){
            cout << sub_str.length();
            return;
        }
        // sub_str = sub_str.substr(0, sub_str.length() - 1);  // 去除最后一个字符
        sub_str = sub_str.substr(0, sub_str.length() - 2);  // 去除最后一个字符
    }
    for(int i=head[index]; i!=-1; i=edge[i].next){
        dfs(edge[i].to);
    }
}

int main(){
    freopen("test.txt", "r", stdin);
    cin >> s;
    n = s.length();
    for(int k=0; k<n; k++){
        // 每个k构建一棵树
        cnt = 0;
        memset(edge, NULL, sizeof(edge));
        memset(head, -1, sizeof(head));
        sub_str = "";
        for(int i=k; i<n; i++){
            for(int j=n-1; j>i; j--) //for(int j=i+1; j<n; j++)
            {
                // cout << s[i] << " " << s[j] << endl;
                // cout << s[i]-'a' << " " << s[j]-'a' << endl;
                add(s[i]-'a', s[j]-'a');
            }
        }
        // printg(k, n);
        // 深度优先遍历
        dfs(k);
        // cout << endl;
        
    }
    return 0;
}

https://www.nowcoder.com/practice/5bfb74efcd5449e69a480550b1fef431?tpId=98&tqId=32846&tPage=1&rp=1&ru=/ta/2019test&qru=/ta/2019test/question-ranking

只能过60%的测试样例
您的代码已保存
段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起
case通过率为66.67%

#include <iostream>
#include <cstring>
#include <string>

using namespace std;
const int maxn= 100+10, maxe=(maxn-1)*maxn/2;
string s;
int n;

struct node{
    int to;  // 到达的节点，该节点
    int next;  // 下一条跳节点
}edge[maxe];

int head[maxn];
int cnt;
int max_len=0;

void add(int u, int v){  // 从u到v
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
    cnt++;
}

void printg(int k, int n){
    for(int u=k; u<n; u++){
        // cout << u << " " << head[u] << " ";
        cout << u << " ";
        for(int i=head[u]; i!=-1; i=edge[i].next){
            cout << "--->" << i << ":(" << edge[i].to << " " <<  edge[i].next << ")";
        }
        cout << endl;
    }
}

string sub_str;

bool huiwen(string str){
    for(int i=0; i<str.length()/2; i++){
        if(str[i] != str[str.length()-i-1])
            return false;
    }
    return true;
}
bool for_break;
void dfs(int index){
    // cout << index;
    // sub_str += char(index+'a');
    sub_str += s[index];
    if(head[index] == -1){
        // cout << index << endl;
        // cout << head[index] << endl;
        // cout << sub_str << endl;
        if(huiwen(sub_str)){
            // cout << sub_str << endl;
            cout << sub_str.length() <<endl;
            for_break = true;
            return;
        }
        // sub_str = sub_str.substr(0, sub_str.length() - 1);  // 去除最后一个字符
        sub_str = sub_str.substr(0, sub_str.length() - 2);  // 去除最后2个字符
        // cout << sub_str << endl;
    }
    for(int i=head[index]; i!=-1; i=edge[i].next){
        dfs(edge[i].to);
        if(for_break) break;  // 跳出多个dfs循环
    }
}

int main(){
    freopen("test.txt", "r", stdin);
    cin >> s;
    n = s.length();
    for(int k=0; k<n; k++){
        // 每个k构建一棵树
        cnt = 0;
        memset(edge, NULL, sizeof(edge));
        memset(head, -1, sizeof(head));
        sub_str = "";
        for(int i=k; i<n; i++){
            for(int j=n-1; j>i; j--) //for(int j=i+1; j<n; j++)
            {
                // cout << i << " " << j << endl;
                // cout << s[i] << " " << s[j] << endl;
                // cout << s[i]-'a' << " " << s[j]-'a' << endl;
                add(i, j);
            }
        }
        // printg(k, n);
        // 深度优先遍历
        for_break = false;
        dfs(k);
        if(sub_str.length()>1){
            break;
        }
        // cout << endl;
    }
    return 0;
}

但是自己还是很开心，写了链式前向星的代码，完成了一些突破。
综合来说，dp还是大杀器，要好好学习。之后也会更些dp的代码

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 194,670评论 5赞 460
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 81,928评论 2赞 371
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 141,926评论 0赞 320
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,238评论 1赞 263
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,112评论 4赞 356
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,138评论 1赞 272
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,545评论 3赞 381
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,232评论 0赞 253
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,496评论 1赞 290
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,596评论 2赞 310
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,369评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,226评论 3赞 313
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,600评论 3赞 299
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 28,906评论 0赞 17
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,185评论 1赞 250
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,516评论 2赞 341
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,721评论 2赞 335

图

字符串 子串树

推荐阅读更多精彩内容

字符串子串树