/*題意：有向圖，求這樣的點(diǎn)的數(shù)量：所有點(diǎn)都能到達(dá)它.縮點(diǎn)成有向無(wú)環(huán)圖，思：如果該強(qiáng)連通有出度，那么 從該出度出去的邊必然回不來(lái)（已經(jīng)縮點(diǎn)了），所以有出度的強(qiáng)連通必然不是。那么是不是所有出度為0的強(qiáng)連通 分量都是呢？顯然不是，如果存在多個(gè)出度為0的強(qiáng)連通，他們必然無(wú)解（他們之間必然不連通）。 任然遍歷邊，判斷不在一個(gè)連通分量中的邊（即為縮點(diǎn)后的邊）和點(diǎn)，考察期出度即可。*/ #include<iostream> //329ms，1A，基礎(chǔ)題。 #include<vector> #include<cstdio> #include<cstring> #include<stack> #include<queue> using namespace std; int n;int m; const int MAX=10001; vector<vector<int> >edges(MAX); int visited[MAX]; int low[MAX]; int dfn[MAX]; bool has_outd[MAX]; //是否有出度 int Strongly_connected_branch[MAX]; //并為一個(gè)強(qiáng)連通，標(biāo)記為1.2.3... int num;int times; bool is_popular[MAX]; //整個(gè)強(qiáng)連通分支i是否有出度，其中一個(gè)點(diǎn)有即有 stack<int>s; bool instack[MAX]; int num_of_popular; //統(tǒng)計(jì)最終數(shù)量 void tarjan(int u) {low[u]=dfn[u]=times++;instack[u]=1;s.push(u);int len=edges[u].size();for(int i=0;i<len;i++){int v=edges[u][i];if(visited[v]==0) {visited[v]=1;tarjan(v);if(low[u]>low[v])low[u]=low[v];}else if(instack[v]&&low[u]>dfn[v]) //有向圖，要問(wèn)是否在棧中，后向邊，V為U某個(gè)祖先{low[u]=dfn[v];}}if(dfn[u]==low[u]) //在一個(gè)SCC{num++;int temp;do{temp=s.top();instack[temp]=0;s.pop();Strongly_connected_branch[temp]=num;} while(temp!=u);} } void initialize() //初始化 {num_of_popular=num=times=0;for(int i=0;i<=n;i++){has_outd[i]=instack[i]=low[i]=dfn[i]=visited[i]=0;edges[i].clear();is_popular[i]=1;Strongly_connected_branch[i]=-1;} } bool readin() {scanf("%d",&n);scanf("%d",&m);initialize();int from,to;for(int i=1;i<=m;i++){scanf("%d%d",&from,&to);edges[from].push_back(to);}return 1; } void solve() {for(int i=1;i<=n;i++)if(visited[i]==0){visited[i]=1;tarjan(i);}for(int i=1;i<=n;i++) //自己思得：枚舉所有邊，縮點(diǎn)只是把所有SCC分開(kāi){int len=edges[i].size();for(int j=0;j<len;j++){int v=edges[i][j];if(Strongly_connected_branch[v]!=Strongly_connected_branch[i])//不在用一個(gè)強(qiáng)連通分支{has_outd[i]=1; //i所在強(qiáng)連通分量有出度is_popular[Strongly_connected_branch[i]]=0; //其所在強(qiáng)連通全跪！break;}}}queue<int>q;for(int i=1;i<=n;i++) //統(tǒng)計(jì)期所在強(qiáng)連通出度為0的點(diǎn){if(is_popular[Strongly_connected_branch[i]]==0){continue;}if(has_outd[i]==0)q.push(i);}int te=Strongly_connected_branch[q.front()];while(!q.empty()) //判斷他們是否都在一個(gè)強(qiáng)連通中，否則跳出，無(wú)解。{int cur=q.front();if(te!=Strongly_connected_branch[cur]){printf("0\n");return;}num_of_popular++;q.pop();te=Strongly_connected_branch[cur];}printf("%d\n",num_of_popular); } int main() {readin();solve();return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/yezekun/p/3925814.html

總結(jié)

以上是生活随笔為你收集整理的poj2186 求有向图G中所有点都能到达的点的数量的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。