模拟无向图

在开始之前，我们先要明白有向图和无向图是什么。

1.无向图：

由顶点和边组成，顶点就像城市中的十字路口；边就像是一座城之中的马路，由于是无向图，所以每条马路都可以来回走，是双向的。如：

这就是一个无向图。

2. 有向图：

也由顶点和边组成，但不同的是，有向图的马路不能来回走，只能单向走，就像马路中的单行道，是单向的，如果想双向，就得再修一条马路。如：

这就是一个有向图。

OK，

相信你一进明白了有向图与无向图的定义下面就让我们用无向图来解决问题吧。

• 聪明的你一定发现了，题目中的样例解释中有一张图： 你肯定能看出来，“欸！这不就是无向图吗？”是的，这道题目本质上就是一个无向图，只要我们构建出一个无向图，这题就简单了：
• 与顶点1直接相连的就是密切接触者，而从顶点1走过两条边可以达到的就是，次密切接触者。
• 那么问题来了，如何模拟无向图呢？

模拟无向图的方法

• 顶点我们可以轻易地模拟出来，就是1—n嘛，边呢？
• 其实我们可以用一个二维数组储存边。储存边不就是储存边的 起始顶点和结束顶点吗，这就简单了，我们把二维数组的第一个数看成边的起始顶点，第二个数看成结束顶点，如果没有这条边的话a[b][c]就设成0，有的话就设成1，这不就行了吗。

数组模拟无向图的基本操作。

1. 找到与顶点b相邻的所有其他顶点。
   • 遍历 a[b][1—100]，这样就可以找出相邻的1—100的顶点了，”1—100“是可以调的，视情况而定。
2. 输入边
   • 输入起始点b，结束顶点c，把a[b][c]和a[c][b]都设为1，设两个的原因是这是无向图，b到c和c到b都可以走。

解题思路

前面讲了这么多，终于开始讲解题思路了。

1. 输入n，m。
2. 输入m行数，每输入一行b和c，就构建一条边（参考基本操作二）。
3. 输出密切接触者：找到与1相邻的所有顶点（参考基本操作一），输出，并且保存到数组bz中（以后要用）。这些就是密切接触者了。
4. 找到 次密切接触者：遍历密切接触者数组，对每个密切接触者顶点，都进行一次基本操作一，并保存到数组da中（因为题目要求从小到大，不重复输出）。
5. 排序次密切接触者：排序的话我建议用计数排序或是sort，因为计数排序稍微改一下，就可以做到排序同时去重的效果，而sort写起来快。
6. 去重输出次密切接触者：如果用的是计数排序，那么直接输出即可，提示，如果计数的数组第i项不为0，直接输出i即可。如果是sort则判断前一项与后一项不同再输出。

AC代码（编写不易，求赞求赞啊）（解析在注释中）

int az[105][105],n,m,a,b,bz[501],num=1,da[101],num_da;
int main()
{
    cin>>n>>m;//解题思路的第一步。
    for (int i=1;i<=m;i++)
    {
        cin>>a>>b;
        az[a][b]=1;
        az[b][a]=1;
    }//第二步，输入边。
    for (int i=2;i<=n;i++)
    {
        if (az[1][i]==1)
        {
            cout<<i<<" ";
            bz[num]=i;//存到数组中，以便后面使用。
            num++;//用于存储第一个没有存数的bz的下标。
        }
    }//运用基本操作一输出密切接触者（第三步）。
    cout<<endl;
    for (int i=1;i<num;i++)
    {//遍历数组bz
        for (int i2=2;i2<=n;i2++)
        {
            if (az[bz[i]][i2]==1 && (az[1][i2]!=1 && az[i2][1]!=1))//注意！其他密接与1也与这个次密接相邻，要去除掉。
            {
                da[num_da]=i2;//加入数组da中。
                num_da++;
            }    
        }//运用基本操作二，找出次密接。
    }
    sort(da,da+num_da);//对数组da进行升序排序（第五步）。
    for (int i=0;i<num_da;i++)
    {
        if (da[i-1]!=da[i])//去重（第六步）。
            cout<<da[i]<<" ";//输出答案。
    }
    return 0;
}

#include <iostream>      //导入模块
#include <algorithm>
#include <cstring>
#include <vector>        //这题我用了向量
using namespace std;
int n,m,sum[105],sc[105];
vector<int> e[10005];
void print()             //调试用，输出每个人接触的人（其实没用）
{
	for (int i = 1;i <= n;i++)
	{
		cout << i << ": ";
		for (int j = 0;j < e[i].size();j++)
		{
			cout << e[i][j] << " ";
		}
		cout << endl;
	}
}
int main()
{
    //加速cin和cout
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	sum[1]++;  //sum[i]表示编号为i的人输出过了，因为1号不要输出，所以直接变成输出过了
	cin >> n >> m;
	for (int i = 1;i <= m;i++)
	{
		int x,y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	sort(e[1].begin(),e[1].end());       //将与1号接触的人排个序，以便输出
	for (int i = 0;i < e[1].size();i++)
	{
		if (sum[e[1][i]] == 0)           //判断是否输出过了
		{
			cout << e[1][i] << " ";
			sum[e[1][i]]++;
		}
	}
	cout << endl;
	memset(sc,0,sizeof(sc));           //为了按顺序输出，我定义了一个sc
	int num = 0;                       //num记录sc里数的个数
	for (int i = 0;i < e[1].size();i++)
	{
		int s = e[1][i];
		for (int j = 0;j < e[s].size();j++)
		{
			if (sum[e[s][j]] == 0)
			{
				sc[num] = e[s][j];
				num++;
				sum[e[s][j]]++;
			}
			
		}
	}
	sort(sc,sc+num);
	for (int i = 0;i < num;i++)
	{
		cout << sc[i] << " ";
	}
	return 0;
}

第二个题解，点赞

struct T
{
    int a, b;//a 和 b 密切接触过
} l[505];

for (int i = 1; i <= m; i++)
{
    //谁跟个一号病人接触了，谁就是一密
    if (l[i].a == 1) mq[l[i].b] = 1;
    if (l[i].b == 1) mq[l[i].a] = 1;
}
mq[1] = 10;
for (int i = 1; i <= m; i++)
{
    int x = l[i].a, y = l[i].b;
    if (mq[x] == 1 && mq[y] == 0)
    {
        mq[y] = 2;//如果遇到了一密就变成二密，1和一密除外
    }
    else if (mq[x] == 0 && mq[y] == 1)
    {
        mq[x] = 2;
    }
}
for (int i = 1; i <= n; i++)
{
    if (mq[i] == 1)
        cout << i << ' ';//查找一密并输出
}
cout << '\n';
for (int i = 1; i <= n; i++)
{
    if (mq[i] == 2)
        cout << i << ' ';//查二密
}

复制

10分代码，各位大佬揪揪错

#include <bits/stdc++.h>
using namespace std;
int n,m,cnt;
int x,y;
int w[505];
bool vis[505];
struct T{
	int a;
	int b;
}s[505];
bool cmp(T l,T r){
	if (l.a==r.a){
		return l.b<r.b;
	}
	return l.a<r.a;
}
int main(){
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		cin>>x>>y;
		s[i].a=min(x,y);
		s[i].b=max(x,y);
	}
	sort(s+1,s+m+1,cmp);
	for (int i=1;i<=n;i++){
		if (s[i].a==1&&vis[s[i].b]!=true){
			cout<<s[i].b<<" ";
			vis[s[i].b]=true;
			cnt++;
			w[cnt]=s[i].b;
		}
	}
	cout<<endl;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=cnt;j++){
			if ((s[i].a==w[j]&&s[i].b!=1)||(s[i].b==w[j]&&s[i].a!=1)){
				if (s[i].a==w[j]){
					if (vis[s[i].b]!=true){
						cout<<s[i].b<<" ";
						vis[s[i].b]=true;
					}
				}
				else{
					if (vis[s[i].a]!=true){
						cout<<s[i].a<<" ";
						vis[s[i].a]=true;
					}
				}
			}
		}
	}
	return 0;
} 

遍历两遍关联关系，算出来密切接触者（L1），及密切接触者的密切接触者（L2）。

    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i] >> b[i];
        if (a[i] == 1)
            L1[b[i]] = true;
        if (b[i] == 1)
            L1[a[i]] = true;
    }
    for (int i = 1; i <= m; i++)
    {
        if (L1[a[i]] == true)
            L2[b[i]] = true;
        if (L1[b[i]] == true)
            L2[a[i]] = true;
    }
    for (int i = 2; i <= n; i++)
        if (L1[i])
            cout << i << " ";
    cout << "\n";
    for (int i = 2; i <= n; i++)
        if (L2[i] && !L1[i])
            cout << i << " ";
    cout << "\n";

嗯，单源最短路。

然后我写了一个bellman-ford，WA，（因为我太蒻了，理论上讲是能过的，各位可以自己试试）

仔细一看，边权均为1。

嗯，bfs。

然后就简单了。AC成功。

时间复杂度O(n^2),空间O(n^2).

友情提示："WA"和"AC"可以点，是我的提交记录。

bool g[101][101],vis[101];
int n,m,dis[101]={0,0};;
vector<int> ans1,ans2;
void bfs(){
	queue<int> q;
	q.push(1);
	dis[1]=0;
	vis[1]=1; 
	//bfs初始化 
	while(!q.empty()){
		int cur = q.front();q.pop();//弹出 
		for(int i = 1 ; i <= n ; ++i){
			if(g[cur][i]&&(!vis[i])){//bfs，注意vis是以点为对象的 
				dis[i]=dis[cur]+1;//处理 
				q.push(i);
				vis[i]=1;
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i = 1 ; i <= m ; ++i){
		scanf("%d%d",&u,&v);//建图，无向的那种 
		g[u][v]=1;
		g[v][u]=1;
	}//读入 
	bfs();
	for(int i = 2 ; i <= n ; ++i){
		if(dis[i]==1)//读取答案 
			ans1.push_back(i);
		else if(dis[i]==2)
			ans2.push_back(i);
	}
	for(int i = 0 ; i < ans1.size() ; ++i)
		printf("%d ",ans1[i]);
	printf("\n");
	for(int i = 0 ; i < ans2.size() ; ++i)
		printf("%d ",ans2[i]);
	//输出 
}

ps:莫复制，否则CE将是你的命运所在

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
} 

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。

#include <bits/stdc++.h>
using namespace std;
int n, m, a[500], b[500], Close1[500], Close 2[500];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i] >> b[i];
        if (a[i] == 1)
            Close1[b[i]] = true;
        if (b[i] == 1)
            Close1[a[i]] = true;
    }
    for (int i = 1; i <= m; i++)
    {
        if (Close1[a[i]] == true)
            Close2[b[i]] = true;
        if (Close1[b[i]] == true)
            Close2[a[i]] = true;
    }
    for (int i = 2; i <= n; i++)
        if (Close1[i])
            cout << i << " ";
    cout << "\n";
    for (int i = 2; i <= n; i++)
        if (Close2[i] && !Close1[i])
            cout << i << " ";
    cout << "\n";
    return 0;
}