数据结构上机复习五

1.顺序创建图，删除

#include <iostream>
#include <cstring>
using namespace std;
const int N = 20010;
int n, m;
int h[N], e[N], ne[N], w[N], idx=0;

void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c;
	if (h[a] == -1 || b < e[h[a]])
		ne[idx] = h[a], h[a] = idx++;
	else
	{
		int t = h[a], pre = h[a];
		while (b > e[t] && t != -1)
			pre = t, t = ne[t];
		ne[idx] = t, ne[pre] = idx++;
	}
}
void Del(int a,int b)
{
	if (e[h[a]] == b) 
	{
		h[a] = ne[h[a]];
	}
	else
	{
		int t = h[a];
		int pre = t;
		while (e[t] != b)
			pre = t, t = ne[t];
		ne[pre] = ne[t];
	}
	
}
int main()
{
	memset(h, -1, sizeof h);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
	}
	int k;
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		int a, b;
		cin >> a >> b;
		Del(a, b);
	}
	for (int i = 0; i < n; i++)
	{
		if (h[i] == -1) continue;
		printf("%d:", i);
		for (int j = h[i]; j != -1; j = ne[j])
		{
			int k = e[j];
			printf("(%d,%d,%d)", i, k, w[j]);
		}
		cout << endl;
	}
}

2.dfs

#include <iostream>
#include <cstring>
using namespace std;
const int N = 20010;
int h[N], e[N], ne[N], idx;
int n, m;
int st[N];
void add(int a, int b)
{
	e[idx] = b;
	if (h[a] == -1 || b < e[h[a]])
		ne[idx] = h[a], h[a] = idx++;
	else
	{
		int t = h[a], pre = h[a];
		while (b > e[t] && t != -1)
			pre = t, t = ne[t];
		ne[idx] = t, ne[pre] = idx++;
	}
}

void dfs(int u)
{
	st[u] = 1;
	cout << u <<" ";
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		if (!st[j])
		{
			dfs(j);
		}
	}
}
int main()
{
	cin >> n >> m;
	memset(h, -1,sizeof h);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
	}
	for (int i = 0; i < n; i++)
		if (!st[i])
			dfs(i);
}

3.字典序最小

#include <iostream>
#include <stack>
#include <queue> 
using namespace std;

const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;

struct Edge {
    int veradj;
    int cost;
    Edge* link;
};
struct Vertex {
    int vername;
    Edge* adjacent;
};

Vertex Head[N];

void CreateGraph(int n,int e)
{
    for(int i=0;i<n;i++)
    {
        Head[i].vername=i;
        Head[i].adjacent=NULL;
    }
    for(int i=0;i<e;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        Edge* t=new Edge;
        t->veradj=b,t->cost=c,t->link=NULL;
        if(Head[a].adjacent==NULL) Head[a].adjacent=t;
        else
        {
            Edge* p=Head[a].adjacent;
            Edge* pre=NULL;
            if(b<p->veradj)
            {
                t->link=p;
                Head[a].adjacent=t;
            }
            else
            {
                while(p!=NULL&&b>p->veradj)
                {
                    pre=p;
                    p=p->link;
                }
                t->link=p;
                pre->link=t;
            }
            
        }
    }
}

int findMin(int S[], int dist[], int n, priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>& pq) {
    while (!pq.empty()) {
        int v = pq.top().second;
        pq.pop();
        if (S[v] == 0) {
            return v;
        }
    }
    return -1;
}

void Dijkstra(Vertex Head[], int n, int u, int dist[], int pre[], int minlen[]) {
    int S[N] = {0};
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    for (int i = 0; i < n; i++) {
        pre[i] = -1;
        dist[i] = INF;
        minlen[i] = INF;
    }

    dist[u] = 0;
    minlen[u] = 1;
    pq.push({0, u});  // 将起始节点加入 priority_queue

    while (!pq.empty()) {
        int v = findMin(S, dist, n, pq);
        if (v == -1)
            break;

        S[v] = 1;
        for (Edge* p = Head[v].adjacent; p != NULL; p = p->link) {
            int w = p->veradj;
            if (S[w] == 0 && dist[v] + p->cost < dist[w]) {
                dist[w] = dist[v] + p->cost;
                pre[w] = v;
                minlen[w] = minlen[v] + 1;
                pq.push({dist[w], w});  // 更新距离后将新节点加入 priority_queue
            } else if (S[w] == 0 && dist[v] + p->cost == dist[w] && minlen[v] + 1 < minlen[w]) {
                minlen[w] = minlen[v] + 1;
                pre[w] = v;
            } else if (S[w] == 0 && dist[v] + p->cost == dist[w] && minlen[v] + 1 == minlen[w]) {
                int a = v, b = pre[w];
                while (pre[a] != pre[b]) {
                    a = pre[a];
                    b = pre[b];
                }
                if (a < b)
                    pre[w] = v;
            }
        }
    }
}

void findPath(int pre[], int v) {
    stack<int> path;
    while (v != -1) {
        path.push(v);
        v = pre[v];
    }
    while (!path.empty()) {
        cout << path.top();
        path.pop();
        if (!path.empty())
            cout << "->";
    }
    cout << endl;
}

int main() {
    int n, e;
    cin >> n >> e;
    CreateGraph(n, e);

    int dist[N], pre[N], minlen[N];
    Dijkstra(Head, n, 0, dist, pre, minlen);
    for (int i = 1; i < n; i++) {
        if (dist[i] != INF) {
            findPath(pre, i);
        }
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;
const int N = 20010;
const int INF = 0x3f3f3f3f;
int h[N], e[N], ne[N], w[N], idx;
int n, m;
int dist[N], st[N],pre[N],minlen[N];
typedef pair<int, int>PII;
void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra()
{
	memset(dist, INF, sizeof dist);
	dist[0] = 0;
	priority_queue<PII, vector<PII>, greater<PII>>pq;
	pq.push({ 0,0 });
	while (!pq.empty())
	{
		auto t = pq.top();
		pq.pop();
		int ver = t.second;
		if (st[ver]) continue;

		for (int i = h[ver]; i != -1; i = ne[i])
		{
			int j = e[i];
			if (!st[j] && dist[j] > dist[ver] + w[i])
			{
				dist[j] = dist[ver] + w[i];
				minlen[j] = minlen[ver] + 1;
				pre[j] = ver;
				pq.push({ dist[j],j });
			}
			else if (!st[j] && dist[j] == dist[ver] + w[i] && minlen[ver] + 1 < minlen[j])
			{
				minlen[j] = minlen[ver] + 1;
				pre[j] = ver;
			}
			else if (!st[j] && dist[j] == dist[ver] + w[i] && minlen[j] == minlen[ver] + 1)
			{
				int a = ver, b = pre[j];
				while (pre[a] != pre[b])
				{
					a = pre[a];
					b = pre[b];
				}
				if (a < b)
					pre[j] = ver;
			}
		}
	}
}
void findpath(int u)
{
	stack<int>s;
	while (u != -1)
	{
		s.push(u);
		u = pre[u];
	}
	while (!s.empty())
	{
		cout << s.top();
		s.pop();
		if (!s.empty())
			cout << "->";
	}
	cout << endl;
}
int main()
{
	cin >> n >> m;
	memset(h, -1,sizeof h);
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
	}
	pre[0] = -1;
	dijkstra();
	for (int i = 1; i < n; i++)
	{
		findpath(i);
	}
}