欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode:802. 找到最终的安全状态(图)

程序员文章站 2022-07-15 09:50:01
...

题目:

leetcode:802. 找到最终的安全状态(图)

分析:

思路很简单,就是找图中的环。
题解思路:
反向的拓扑排序
leetcode:802. 找到最终的安全状态(图)
一个图中,如果没有入度为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;
    }
};

leetcode:802. 找到最终的安全状态(图)