leetcode:802. 找到最终的安全状态(图)
程序员文章站
2022-07-15 09:50:01
...
题目:
分析:
思路很简单,就是找图中的环。
题解思路:
反向的拓扑排序
一个图中,如果没有入度为0的点,那么所有的点都在图上。
代码1:超时:提醒自己:图,不要总是想着用最基本的邻接的那个二维矩阵:
vector<vector<int> > g;
int A[g.size()][g.size()];//A[i][j] i->j
memset(A,0,sizeof(A));
for(int i=0;i<g.size();i++)
{
for(int j=0;j<g[i].size();j++)
{
A[g[i][j]][i]=1;//箭头反向。
}
}
vector<int> v;
set<int> s;
while(1)
{
//入度为0的点,即列上全为0。
int loca=-1;
for(int i=0;i<g.size();i++)
{
int ok=1;
for(int j=0;j<g.size();j++)
{
if(A[j][i]==1){
ok=0;
break;
}
}
if(ok==0) continue;
//i列全为0了
if(s.count(i)==1) continue;
//1
s.insert(i);
v.push_back(i);
//出度撤销
for(int k=0;k<g.size();k++)
A[i][k]=0;
loca=1;
break;
}
if(loca==-1) break;
}
sort(v.begin(),v.end());
return v;
代码2:寻找上面复杂的原因,每次找到入度为0的点。优化后,还是超时,哎
vector<vector<int> > g;
queue<int> q;
vector<int> v;
map<int,int> m;
vector<vector<int> > rg(g.size(),vector<int>);
//反向
for(int i=0;i<g.size();i++)
{
for(int j=0;j<g[i].size();j++)
{
g[g[i][j]].push_back(i);
}
//寻找g中出度为0的点。即g【i】为空。
if(g.size()==0)
{
q.push(i);
}
}
//寻找g中出度为0的点。即g【i】为空。
while(1)
{
if(q.size()==0) break;
int c=q.front();
q.pop();
//安全吗? 用g
int ok=1;
for(int i=0;i<g[c].size();i++)
{
if(m[g[c][i]]=0) {
ok=0;
break;
}
}
if(ok)
{
m[c]=1;
v.push_back(c);
//加入新的可能的 用rg
for(int i=0;i<rg[c].size();i++)
{
if(m[rg[c][i]]) continue;
queue<int> qq=q;
int cc=1;
while(!qq.empty())
{
if(rg[c][i]==qq.front())
{
cc=0;
break;
}
qq.pop();
}
if(cc) q.push(rg[c][i]);
}
}
}
sort(v.begin(),v.end());
return v;
再看题解,直接用数组记录了度数:
class Solution {
public:
vector<int> eventualSafeNodes(vector<vector<int>>& g) {
queue<int> q;
vector<int> v;
map<int,int> m;
vector<vector<int> > rg(g.size(),vector<int>());
int A[g.size()];
memset(A,0,sizeof(A));
//反向
for(int i=0;i<g.size();i++)
{
for(int j=0;j<g[i].size();j++)
{
rg[g[i][j]].push_back(i);
}
//寻找g中出度为0的点。即g【i】为空。
if(g[i].size()==0)
{
q.push(i);
}
A[i]=g[i].size();
}
//寻找g中出度为0的点。即g【i】为空。
cout<<q.size();
while(1)
{
if(q.size()==0) break;
int c=q.front();
q.pop();
v.push_back(c);
for(int i=0;i<rg[c].size();i++)
{
A[rg[c][i]]--;
if(A[rg[c][i]]==0) q.push(rg[c][i]);
}
}
sort(v.begin(),v.end());
return v;
}
};