PAT L2-038. 天梯赛 L2-038 (dfs)
原题链接
简单
作者:
Lss_lmj
,
2022-02-24 16:22:02
,
所有人可见
,
阅读 162
C++ 代码
#include <bits/stdc++.h>
using namespace std;
vector<int> e[10010], temp, ans;
int n, maxx = -1;
bool book[10010];
int que[10010];
void dfs(int u, int k)
{
if (k > maxx)//如果路径长度比现有长度更长
{
maxx = k;//更新最大长度
ans = temp;//更新最大长度的序列
}
for (int i = 0; i < e[u].size(); i++)
{
temp.push_back(e[u][i]);//模拟每一步
dfs(e[u][i], k + 1);
temp.pop_back();//不要忘记pop出来
}
return;
}
int main(int argc, char const *argv[])
{
cin >> n;
for (int i = 0; i < n; i++)
{
int t;
cin >> t;
while (t--)
{
int x;
cin >> x;
book[x] = 1;
e[i].push_back(x);
}
sort(e[i].begin(), e[i].end());//从小到大排序,这样如果能找到最大路径的话一定是最小序列
}
int flag;//病毒源头
for (int i = 0; i < n; i++)
if (book[i] == 0)
{
flag = i;
break;
}
dfs(flag, 0);
printf("%d\n", maxx + 1);
printf("%d", flag);
for (int i = 0; i < ans.size(); i++)
printf(" %d", ans[i]);
printf("\n");
return 0;
}
您好,其实这个代码是有问题的,只不过测试数据并没有出到,以下的数据能测试
快想破头了,救救废物
你这个数据中0和其他编号病毒不同源