leetcode：802. 找到最终的安全状态（图）_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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

代码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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

再看题解，直接用数组记录了度数：

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40