題意：
? ? ? 給你一個有向圖，然后問你有多少個滿足要求的點，要求是： 這個點能走到的所有點都能走回這個點，找到所有的這樣的點，然后排序輸出。


思路：

? ? ? 可以直接一遍強連通縮點，所點之后出度為0的強連通點中所包含的點都是滿足要求的，比較容易理解，在強連通里，所有點都能走回來，同時只要強連通所點后沒有出度，那么就能保證里面的每個點到所有連接自己連接的點后都能走回來，還有就是這個題目我數組開到快 80000000了，還沒MLE，這個我就不說什么了。

#include<stdio.h> #include<string.h> #include<stack> #include<algorithm>#define N_node 5001 #define N_edge 5000 * 5000 + 1using namespace std;typedef struct {int to ,next; }STAR;typedef struct {int a ,b; }EDGE;EDGE edge[N_edge]; STAR E1[N_edge] ,E2[N_edge]; int list1[N_node] ,list2[N_node] ,tot; int Belong[N_node] ,Cnt; int mark[N_node] ,Ans[N_node]; stack<int>sk;void add(int a ,int b) {E1[++tot].to = b;E1[tot].next = list1[a];list1[a] = tot;E2[tot].to = a;E2[tot].next = list2[b];list2[b] = tot; }void DFS1(int x) {mark[x] = 1;for(int k = list1[x] ;k ;k = E1[k].next){int to = E1[k].to;if(mark[to]) continue;DFS1(to);}sk.push(x); }void DFS2(int x) {mark[x] = 1;Belong[x] = Cnt;for(int k = list2[x] ;k ;k = E2[k].next){int to = E2[k].to;if(mark[to]) continue;DFS2(to);} }int main () {int n ,m ,i ,a ,b;while(~scanf("%d" ,&n) && n){scanf("%d" ,&m);memset(list1 ,0 ,sizeof(list1));memset(list2 ,0 ,sizeof(list2));tot = 1;for(i = 1 ;i <= m ;i ++){scanf("%d %d" ,&a ,&b);edge[i].a = a ,edge[i].b = b;add(a ,b);}memset(mark ,0 ,sizeof(mark));while(!sk.empty()) sk.pop();for(i = 1 ;i <= n ;i ++)if(!mark[i]) DFS1(i);memset(mark ,0 ,sizeof(mark));Cnt = 0;while(!sk.empty()){int xin = sk.top();sk.pop();if(mark[xin]) continue;Cnt ++;DFS2(xin);}memset(mark ,0 ,sizeof(mark));for(i = 1 ;i <= m ;i ++){a = Belong[edge[i].a];b = Belong[edge[i].b];if(a == b) continue;mark[a] ++;}int nowid = 0;for(i = 1 ;i <= n ;i ++)if(!mark[Belong[i]]) Ans[++nowid] = i;sort(Ans + 1 ,Ans + nowid + 1);for(i = 1 ;i <= nowid ;i ++)if(i == nowid) printf("%d\n" ,Ans[i]);else printf("%d " ,Ans[i]);}return 0; }

總結

以上是生活随笔為你收集整理的POJ2553 强连通出度为0的应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。