DFS 单链表存储 大根堆处理输入
保姆级详解
算法
(暴力DFS + 单链表存储图) $O(nm)$
时间复杂度
实际上经过优化 远远不到O(nm)的时间复杂度
不然o.4秒也AC不掉了
C++ 代码
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
const int N = 110000;
const int M = 1100000;
int h[N],ne[M],idx,e[M];
bool ocu[N];
int n;
vector<int> ans;
// 此处一定要加 & 引用 不然vector每一层太多会爆空间
void dfs(int node, vector<int> &last)
{
if(h[node] == -1)
{
if(last.size()>ans.size())
ans = last;
}
for(int i = h[node];~i;i=ne[i])
{
int nod = e[i];
ocu[nod] = 1;
last.push_back(nod);
dfs(nod,last);
last.pop_back();
}
}
void add(int a, int b)
{
e[++idx] = b;
ne[idx] = h[a];
h[a] = idx;
}
int main()
{
memset(h,-1,sizeof h);
cin>>n;
for(int i=0;i<n;i++)
{
int k,linknode;
cin>>k;
priority_queue<int,vector<int>, less<int>> que;
for(int j=0;j<k;j++)
{
cin>>linknode;
que.push(linknode);
}
// 这里必须使用大根堆来限定加点的顺序
// 因为单链表这里插入点是尾插法,所以que中最后的(也就是编号最小的点)
// 在dfs时会最先被搜索
// 这样就保证了题目要求:(长度一样时,选编号更小的)
while(!que.empty())
{
add(i,que.top());
que.pop();
}
}
for(int i=0;i<n;i++)
{
// enumerate the origin node
// ocu就是枚举源节点的优化
//倘若该节点曾经是别人的链中的一份子,
//则必不可能再是源节点
if(ocu[i]) continue;
vector<int> path;
path.push_back(i);
ocu[i] = 1;
dfs(i,path);
}
cout<<ans.size()<<endl;
for(auto c: ans)
{
cout<<c<<" ";
}
return 0;
}
太强了,终于知道我写的为什么爆内存了,原本是每次都复制了一遍vector数组....