数据结构OJ实验10-图连通与生成树

A. DS图—图的连通分量

题目描述

输入无向图顶点信息和边信息，创建图的邻接矩阵存储结构，计算图的连通分量个数。

输入

测试次数t

每组测试数据格式如下：

第一行：顶点数 顶点信息

第二行：边数

第三行开始，每行一条边信息

输出

每组测试数据输出，顶点信息和邻接矩阵信息

输出图的连通分量个数，具体输出格式见样例。

每组输出直接用空行分隔。

样例查看模式?

正常显示查看格式

输入样例1

3\n
4?A?B?C?D\n
2\n
A?B\n
A?C\n
6?V1?V2?V3?V4?V5?V6\n
5\n
V1?V2\n
V1?V3\n
V2?V4\n
V5?V6\n
V3?V5\n
8?1?2?3?4?5?6?7?8\n
5\n
1?2\n
1?3\n
5?6\n
5?7\n
4?8

输出样例1

A?B?C?D\n
0?1?1?0\n
1?0?0?0\n
1?0?0?0\n
0?0?0?0\n
2\n
\n
V1?V2?V3?V4?V5?V6\n
0?1?1?0?0?0\n
1?0?0?1?0?0\n
1?0?0?0?1?0\n
0?1?0?0?0?0\n
0?0?1?0?0?1\n
0?0?0?0?1?0\n
1\n
\n
1?2?3?4?5?6?7?8\n
0?1?1?0?0?0?0?0\n
1?0?0?0?0?0?0?0\n
1?0?0?0?0?0?0?0\n
0?0?0?0?0?0?0?1\n
0?0?0?0?0?1?1?0\n
0?0?0?0?1?0?0?0\n
0?0?0?0?1?0?0?0\n
0?0?0?1?0?0?0?0\n
3\n

AC代码

//无向图,连通分量个数,用并查集
//无向图连通分量->极大连通子图
#include<iostream>
using namespace std;
class Map
{
    int vertexnum;
    string* vertex;
    int** adjmatrix;
    int* fa;
public:
    Map()
    {
        cin >> vertexnum;
        vertex = new string[vertexnum];
        fa = new int[vertexnum];//初始！
        for (int i = 0; i < vertexnum; i++)
        {
            cin >> vertex[i];
            fa[i] = i;
        }
        adjmatrix = new int* [vertexnum];
        for (int i = 0; i < vertexnum; i++)
        {
            adjmatrix[i] = new int[vertexnum];
            for (int j = 0; j < vertexnum; j++)
            {
                adjmatrix[i][j] = 0;
            }
        }
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            string s1, s2;
            cin >> s1 >> s2;
            int index1 = 0;
            int index2 = 0;
            for (int j = 0; j < vertexnum; j++)
            {
                if (vertex[j] == s1)
                {
                    index1 = j;
                    break;
                }
            }
            for (int j = 0; j < vertexnum; j++)
            {
                if (vertex[j] == s2)
                {
                    index2 = j;
                    break;
                }
            }
            adjmatrix[index1][index2] = 1;
            adjmatrix[index2][index1] = 1;//无向图
            int p1 = find(index1);
            int p2 = find(index2);
            if (p1 != p2)
            {
                fa[p1] = p2;
            }
        }
    }
    int find(int x)
    {
        if (x != fa[x])x=fa[x];
        return fa[x];
    }
    void display_array()
    {
        for (int i = 0; i < vertexnum; i++)
        {
            if (i)
                cout << " ";
            cout << vertex[i];
        }
        cout << endl;
        for (int i = 0; i < vertexnum; i++)
        {
            cout << adjmatrix[i][0];
            for (int j = 1; j < vertexnum; j++)
                cout << " " << adjmatrix[i][j];
            cout << endl;
        }
    }
    ~Map()
    {
        delete[]vertex;
        delete[]fa;
        for (int i = 0; i < vertexnum; i++)
        {
            delete[]adjmatrix[i];
        }
        delete[]adjmatrix;
    }
    int get_connect()
    {
        int cnt = 0;
        for (int i = 0; i < vertexnum; i++)
        {
            if (fa[i] == i)//祖先是自己，不与他人连通即为连通分量
                cnt++;
        }
        return cnt;
    }
};
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        Map m;
        m.display_array();
        cout << m.get_connect() << endl;
        cout << endl;
    }
    return 0;
}

B. 村村通工程（Prim算法）

题目描述

"村村通"是国家一个系统工程，其包涵有：公路、电力、生活和饮用水、电话网、有线电视网、互联网等等。

村村通公路工程，是国家为构建和谐社会，支持新农村建设的一项重大举措，是一项民心工程。又称“五年千亿元”工程

该工程是指中国力争在5年时间实现所有村庄通沥青路或水泥路，以打破农村经济发展的交通瓶颈，解决9亿农民的出行难题。

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

要求用Prim算法求解

输入

第1行：顶点数n

第2行：n个顶点编号

第3行：边数m

接着m行：m条边信息，格式为：顶点1 顶点2 权值

最后一行：Prim算法的起点v

输出

第1行：输出最小生成树的权值之和

接着n-1行对应n-1条边信息

按树的生长顺序输出

样例查看模式?

正常显示查看格式

输入样例1?

6\n
v1?v2?v3?v4?v5?v6?\n
10\n
v1?v2?6\n
v1?v3?1\n
v1?v4?5\n
v2?v3?5\n
v2?v5?3\n
v3?v4?5\n
v3?v5?6\n
v3?v6?4\n
v4?v6?2\n
v5?v6?6\n
v1\n

输出样例1

15\n
v1?v3?1\n
v3?v6?4\n
v6?v4?2\n
v3?v2?5\n
v2?v5?3\n

AC代码

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1000, inf = 0x3f3f3f;
int g[N][N];
int n, m;
map<string, int>mp;
map<int, string>mm;
struct node
{
    int u, v, w;
};
vector<node>edge;
bool cmp(const node& a, const node& b)
{
    return a.w < b.w;
}
void Prim(int x)
{
    int len = inf;
    int end = 0;
    int sum = 0;
    int k = 0;
    vector<node>temp(n + 1);
    //temp[i].u表:i点连接u点
    //temp[i].w表:i到u的距离
    for (int i = 1; i <= n; i++)
    {
        temp[i].u = x;
        temp[i].w = g[x][i];
    }
    temp[x].w = 0;
    for (int i = 1; i < n; i++)
    {
        len = inf;
        //找到x到某点j的最小距离
        for (int j = 1; j <= n; j++)
        {
            if (temp[j].w && temp[j].w < len)
            {
                len=temp[j].w;
                end = j;
            }
        }
        sum += len;
        //更新添加记录边
        edge[k].u = temp[end].u;
        edge[k].v = end;
        edge[k].w = len;
        k++;
        //加入后更新
        for (int j = 1; j <= n; j++)
        {
            if (temp[j].w && temp[j].w > g[end][j])
            {
                temp[j].w = g[end][j];
                temp[j].u = end;
            }
        }
        temp[end].w = 0;
    }
    cout << sum << endl;
    for (int i = 0; i < n - 1; i++)
    {
        cout << mm[edge[i].u] << " " << mm[edge[i].v] << " " << edge[i].w << endl;
    }
}
int main()
{
    memset(g, inf, sizeof(g));
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        mp[s] = i;
        mm[i] = s;
    }
    cin >> m;
    edge.resize(m);
    for (int i = 0; i < m; i++)
    {
        string s1, s2;
        int c;
        cin >> s1 >> s2 >> c;
        g[mp[s1]][mp[s2]] =
            g[mp[s2]][mp[s1]] = c;
        edge[i].u = min(mp[s1], mp[s2]);
        edge[i].v = max(mp[s1], mp[s2]);
        edge[i].w = c;
    }
    sort(edge.begin(), edge.end(), cmp);
    string start;
    cin >> start;
    //Prim算法有起点
    Prim(mp[start]);
    return 0;
}

C. 村村通工程（Kruskal算法）

题目描述

"村村通"是国家一个系统工程，其包涵有：公路、电力、生活和饮用水、电话网、有线电视网、互联网等等。

村村通公路工程，是国家为构建和谐社会，支持新农村建设的一项重大举措，是一项民心工程。又称“五年千亿元”工程

该工程是指中国力争在5年时间实现所有村庄通沥青路或水泥路，以打破农村经济发展的交通瓶颈，解决9亿农民的出行难题。

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

要求用Kruskal算法求解

输入

第1行：顶点数n

第2行：n个顶点编号

第3行：边数m

接着m行：m条边信息，格式为：顶点1 顶点2 权值

输出

第1行：输出最小生成树的权值之和

接着n-1行对应n-1条边信息

如果能找到最小生成树，按树的生长顺序输出,?边顶点按数组序号升序输出

如果输入数据不足以保证畅通，则直接输出?1，无需输出任何边信息

样例查看模式?

正常显示查看格式

输入样例1?

6\n
v1?v2?v3?v4?v5?v6?\n
10\n
v1?v2?6\n
v1?v3?1\n
v1?v4?5\n
v2?v3?5\n
v2?v5?3\n
v3?v4?5\n
v3?v5?6\n
v3?v6?4\n
v4?v6?2\n
v5?v6?6\n

输出样例1

15\n
v1?v3?1\n
v4?v6?2\n
v2?v5?3\n
v3?v6?4\n
v2?v3?5\n

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1000, inf = 0x3f3f3f3f;
struct node
{
    int u, v, w;
};
bool cmp(const node& a, const node& b)
{
    return a.w < b.w;
}
int n, m;
map<string, int>mp;
map<int, string>mm;
string ps;
vector<node>edge;
vector<node>alter;
int g[N][N];
bool st[N];
int p[N];
int find(int x)
{
    if (x != p[x])p[x] = find(p[x]);
    return p[x];
}
void kruskal()
{
    int k = 0;
    int sum = 0;
    vector<node>ans;
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;//初始并查集数组
    }
    for (int i = 0; i < m; i++)
    {
        int u = alter[i].u;
        int v = alter[i].v;
        int w = alter[i].w;
        int pu = find(u);
        int pv = find(v);
        if (pu != pv)
        {
            p[pu] = pv;
            sum += w;//从小到大之间合并
            ans.push_back(alter[i]);
        }
    }
    //判断
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (find(i) != find(j))//判断连通性
            {
                cout << -1 << endl;
                return;
            }
        }
    }
    cout << sum << endl;
    for (int i = 0; i < ans.size(); i++)
    {
        cout << mm[ans[i].u] << " " << mm[ans[i].v] << " " << ans[i].w << endl;
    }
}
int main()
{
    memset(g, inf, sizeof(g));
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        mp[s] = i;
        mm[i] = s;
    }
    cin >> m;
    edge.resize(m);
    for (int i = 0; i < m; i++)
    {
        string s1, s2;
        int c;
        cin >> s1 >> s2 >> c;
        g[mp[s1]][mp[s2]] =
            g[mp[s2]][mp[s1]] = c;
        edge[i].u = min(mp[s1], mp[s2]);
        edge[i].v = max(mp[s1], mp[s2]);
        edge[i].w = c;
    }
    sort(edge.begin(), edge.end(), cmp);
    alter = edge;
    kruskal();
    return 0;
}

D. 汉密尔顿回路

题目描述

著名的“汉密尔顿（Hamilton）回路问题”是要找一个能遍历图中所有顶点的简单回路（即每个顶点只访问 1 次）。本题就要求你判断任一给定的回路是否汉密尔顿回路。

输入

首先第一行给出两个正整数：无向图中顶点数?N（2<N≤200）和边数?M。随后?M?行，每行给出一条边的两个端点，格式为“顶点1 顶点2”，其中顶点从 1 到N?编号。再下一行给出一个正整数?K，是待检验的回路的条数。随后?K?行，每行给出一条待检回路，格式为：

n?V1??V2????Vn?

其中?n?是回路中的顶点数，Vi??是路径上的顶点编号。

输出

对每条待检回路，如果是汉密尔顿回路，就在一行中输出"YES"，否则输出"NO"。

样例查看模式?

正常显示查看格式

输入样例1?

6?10\n
6?2\n
3?4\n
1?5\n
2?5\n
3?1\n
4?1\n
1?6\n
6?3\n
1?2\n
4?5\n
6\n
7?5?1?4?3?6?2?5\n
6?5?1?4?3?6?2\n
9?6?2?1?6?3?4?5?2?6\n
4?1?2?5?1\n
7?6?1?3?4?5?2?6\n
7?6?1?2?5?4?3?1

输出样例1

YES\n
NO\n
NO\n
NO\n
YES\n
NO

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=440;
int g[N][N];
int n,m,k;
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int u,v;
        cin>>u>>v;
        g[u][v]=g[v][u]=1;
    }
    cin>>k;
    while(k--)
    {
       int p;
       cin>>p;
       vector<int>need;
       set<int>ss;
       bool flag=1;
       for(int i=1;i<=p;i++)
       {
            int x;
            cin>>x;
            need.push_back(x);
            if(i!=p &&ss.count(x))//只有起点和终点那个数字可以出现两次
            {
                flag=0;
            }
            ss.insert(x);
       }
       for(int i=0;i<p-1;i+=2)
       {
            if(!g[need[i]][need[i+1]])
            {
                flag=0;
                break;
            }
       }
       if(ss.size()<n||need[0]!=need[p-1])flag=0;
       if(flag)cout<<"YES"<<endl;
       else cout<<"NO"<<endl;
    }
    return 0;
}

E. 六度空间

题目描述

“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”

“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。

假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

输入

输入第1行给出两个正整数，分别表示社交网络图的结点数N（1<N≤10?3??，表示人数）、边数M（≤33×N，表示社交关系数）。随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到N编号）。

输出

对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。

样例查看模式?

正常显示查看格式

输入样例1?

10?9\n
1?2\n
2?3\n
3?4\n
4?5\n
5?6\n
6?7\n
7?8\n
8?9\n
9?10

输出样例1

1:?70.00%\n
2:?80.00%\n
3:?90.00%\n
4:?100.00%\n
5:?100.00%\n
6:?100.00%\n
7:?100.00%\n
8:?90.00%\n
9:?80.00%\n
10:?70.00%

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int inf = 0x3f3f3f3f;
int g[N][N];
int n, m;
void floyd()
{
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)g[i][j] = 0;
            else g[i][j] = inf;
        }
    }
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x][y] = 1;
        g[y][x] = 1;
    }
    floyd();
    for (int i = 1; i <= n; i++)
    {
        int ans = 1;//加上自身
        for (int j = 1; j <= n; j++)
        {
            if (i == j)continue;
            if (g[i][j] <= 6)ans++;
        }
        printf("%d: %.2lf", i, ((ans * 1.0) / n) * 100);
        cout << "%" << endl;
    }
    return 0;
}

F. 红色警报

题目描述

战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。

输入

输入在第一行给出两个整数N（0?<?N?≤?500）和M（≤?5000），分别为城市个数（于是默认城市从0到N-1编号）和连接两城市的通路条数。随后M行，每行给出一条通路所连接的两个城市的编号，其间以1个空格分隔。在城市信息之后给出被攻占的信息，即一个正整数K和随后的K个被攻占的城市的编号。

注意：输入保证给出的被攻占的城市编号都是合法的且无重复，但并不保证给出的通路没有重复。

输出

对每个被攻占的城市，如果它会改变整个国家的连通性，则输出Red Alert: City k is lost!，其中k是该城市的编号；否则只输出City k is lost.即可。如果该国失去了最后一个城市，则增加一行输出Game Over.。

样例查看模式?

正常显示查看格式

输入样例1?

5?4\n
0?1\n
1?3\n
3?0\n
0?4\n
5\n
1?2?0?4?3

输出样例1

City?1?is?lost.\n
City?2?is?lost.\n
Red?Alert:?City?0?is?lost!\n
City?4?is?lost.\n
City?3?is?lost.\n
Game?Over.

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 550, M = 5500;
int p[N];
int n, m;
int k;
bool st[N];
struct node
{
    int u, v;
}e[M];
int count()
{
    int res = 0;
    for (int i = 0; i < n; i++)
    {
        if (p[i] == i && st[i] == 0)//连通分量个数
        {
            res++;
        }
    }
    return res;
}
int find(int x)
{
    if (x != p[x])p[x] = find(p[x]);
    return p[x];
}
void init()
{
    for (int i = 0; i < n; i++)
    {
        p[i] = i;
    }
}
int main()
{
    cin >> n >> m;
    init();
    //路可重复
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[i].u = u;
        e[i].v = v;
        int pu = find(u);
        int pv = find(v);
        if (pu != pv)
        {
            p[pu] = pv;//合并连通
        }
    }
    int cnt = count();//被攻击前的连通分量个数
    cin >> k;//k不重复
    for (int i = 0; i < k; i++)
    {
        int x;
        cin >> x;
        //x被攻击
        st[x] = 1;//不参与合并x
        init();//每次攻击都重新做一遍合并
        for (int j = 0; j < m; j++)
        {
            int u = e[j].u;
            int v = e[j].v;
            if (st[u] == 0 && st[v] == 0)//都可以参与合并
            {
                int pu = find(u);
                int pv = find(v);
                if (pu != pv)
                {
                    p[pu] = pv;
                }
            }
        }
        int cur = count();//攻击后连通分量个数
        if (cur <= cnt)//不破坏连通性
        {
            printf("City %d is lost.\n", x);
        }
        else//连通分量个数增加，连通性改变
        {
            printf("Red Alert: City %d is lost!\n", x);
        }
        cnt = cur;
    }
    //增加的最后判断
    if (k >= n)
    {
        printf("Game Over.");
    }
    return 0;
}