8-7陈老师课堂总结

Crash_Man_CHN · 2025-08-08 09:36:24 · 个人记录

关于图

1.邻接矩阵

方式：本质是用二维数组表示，点与点之间的关系

优点：查询时间很快，O(1)

缺点：空间很大，是n*n,边的数量较多的时候会导致空间过于浪费，并且在重边的时候根本存储不了，并且输出连接一个点的所有边会很慢

2.邻接表

方式：按照边存储，存入一个vector

优点：空间不会浪费，利用率高，并且可以存储重边

缺点：查询太慢

例题

U460099 结点的度

度是什么？

度就是入度+出度，入度为指向这个点的边的个数，出度为这个点出去的边的个数

题目思路

既然度都知道了度是什么，题就简单了，我们可以用两个数组统计入度和出度，最后相加即可

题目代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int in[N],out[N];
//vector<int> v[N];
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,w;
        cin>>u>>w;
        in[u]++;
        out[w]++;
    }
    for(int i=1;i<=n;i++)cout<<in[i]+out[i]<<"\n";
    return 0;
}

U460103 图的类型

看图

题目思路

了解了三种类型之后，我们把输入的点的度给统计一下，然后分类别讨论即可

题目代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,deg[N];
string solve()
{
    int cnt1=0,cnt2=0;
    for(int i=1;i<=n;i++)
    {
        cnt1+=(deg[i]==1);
        cnt2+=(deg[i]==2);
    }
    if(cnt2==n)return "Ring";
    else if(cnt1==2&&cnt2==n-2)return "Chain";
    else if(cnt1==n-1)return "Flower";
    return "Neither";
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        deg[u]++,deg[v]++;
    }
    cout<<solve();
    return 0;
}

B3643 图的存储

题目思路

其实就是邻接矩阵和邻接表的拼好题，只是需要将邻接表排序输出而已

题目代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005;
vector<int> v[N];
int g[N][N];
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,w;
        cin>>u>>w;
        g[u][w]=1;
        g[w][u]=1;
        v[u].push_back(w);
        v[w].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<g[i][j]<<" ";
        }
        cout<<"\n";
    }
    for(int i=1;i<=n;i++)
    {
        cout<<v[i].size()<<" ";
        sort(v[i].begin(),v[i].end(),less<int>());
        for(int j=0;j<v[i].size();j++)cout<<v[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}