牛客網(wǎng)

poj 2553

文章目錄

• • Description
  • 題意：
  • 題解：
  • 代碼：

Description

We will use the following (standard) definitions from graph theory.
Let V be a nonempty and finite set, its elements being called vertices
(or nodes). Let E be a subset of the Cartesian product V×V, its
elements being called edges. Then G=(V,E) is called a directed graph.
Let n be a positive integer, and let p=(e1,…,en) be a sequence of
length n of edges ei∈E such that ei=(vi,vi+1) for a sequence of
vertices (v1,…,vn+1). Then p is called a path from vertex v1 to
vertex vn+1 in G and we say that vn+1 is reachable from v1, writing
(v1→vn+1). Here are some new definitions. A node v in a graph G=(V,E)
is called a sink, if for every node w in G that is reachable from v, v
is also reachable from w. The bottom of a graph is the subset of all
nodes that are sinks, i.e., bottom(G)={v∈V|?w∈V:(v→w)?(w→v)}. You have
to calculate the bottom of certain graphs.

Input

The input contains several test cases, each of which corresponds to a
directed graph G. Each test case starts with an integer number v,
denoting the number of vertices of G=(V,E), where the vertices will be
identified by the integer numbers in the set V={1,…,v}. You may
assume that 1<=v<=5000. That is followed by a non-negative integer e
and, thereafter, e pairs of vertex identifiers v1,w1,…,ve,we with
the meaning that (vi,wi)∈E. There are no edges other than specified by
these pairs. The last test case is followed by a zero.

Output

For each test case output the bottom of the specified graph on a
single line. To this end, print the numbers of all nodes that are
sinks in sorted order separated by a single space character. If the
bottom is empty, print an empty line.

Sample Input

3 3 1 3 2 3 3 1 2 1 1 2 0

Sample Output

1 3 2

題意：

，一個(gè)點(diǎn)所能到達(dá)的任意一個(gè)點(diǎn)都能返回這個(gè)點(diǎn)，那么這個(gè)點(diǎn)稱為bottom點(diǎn)，找出所有的bottom點(diǎn)。
讀入：
第一行 v e（點(diǎn)數(shù)和邊數(shù)）
第二行 具體邊的方向
當(dāng)讀0時(shí)結(jié)束

題解：

先找到圖中所有強(qiáng)連通圖，強(qiáng)連通圖內(nèi)的每個(gè)點(diǎn)都是互通的，然后Tarjan縮點(diǎn)，得到新圖，如果一個(gè)點(diǎn)沒有出去的邊（即出度為0，無須管入度），那么這個(gè)點(diǎn)就符合要求。因?yàn)槲覀円一ハ嗄艿竭_(dá)的點(diǎn)，這又是縮點(diǎn)后的圖，一個(gè)點(diǎn)有出度，肯定不能再返回。
大致是這個(gè)意思，好好想想，這算是Tarjan的模板題
（讀題太費(fèi)勁了。。。）

代碼：

#include<bits/stdc++.h> #define mem(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=5020; vector<int>v[maxn]; int n,m,x,y,k,top,num,inf; int pos[maxn],vis[maxn],low[maxn],dnf[maxn]; int ans[maxn],cnt[maxn],degree[maxn]; void init() {k=0;top=0;num=0;for(int i=0;i<=n;i++)v[i].clear();mem(vis);mem(pos);mem(ans);mem(cnt);mem(dnf);mem(low);mem(degree); } void tarjan(int u) {dnf[u]=low[u]=++k;pos[++top]=u;vis[u]=1;for(int i=0;i<v[u].size();i++){int to=v[u][i];if(!dnf[to]){tarjan(to);low[u]=min(low[u],low[to]);}else if(vis[to])low[u]=min(low[u],dnf[to]);}//以上為正常的tarjan求強(qiáng)連通分量 if(low[u]==dnf[u]){num++;while(1){inf=pos[top--];//棧中最上面的點(diǎn) ans[inf]=num;// 同一連通分量的點(diǎn)上相同的顏色，相當(dāng)于縮點(diǎn) vis[inf]=0;//if(inf==u)break;//遍歷完后退出 }} } void dfs(int u) {cnt[u]=ans[u];//給點(diǎn)標(biāo)記，防止重復(fù)搜索 for(int i=0;i<v[u].size();i++){int to=v[u][i];if(ans[u]!=ans[to])degree[ans[u]]++;//如果這個(gè)點(diǎn)有出度，值++ if(!cnt[to])dfs(to);//如果指向的點(diǎn)沒被搜索過 } } void solve() {for(int i=1;i<=n;i++)if(!dnf[i])tarjan(i);//如果這個(gè)點(diǎn)還沒走過 for(int i=1;i<=n;i++)if(!cnt[i])dfs(i);//如果這個(gè)點(diǎn)沒被走過 bool flag=1;for(int i=1;i<=n;i++){if(!degree[ans[i]])//判斷這個(gè)點(diǎn)是否有出度 {if(flag)//這里主要是為了控制格式，第一個(gè)不帶空格，后面帶空格 {printf("%d",i);flag^=1;}else printf(" %d",i);}}cout<<endl; } int main() {while(cin>>n&&n){cin>>m;init();//初始化所有數(shù)組與值 for(int i=0;i<m;i++){cin>>x>>y;v[x].push_back(y);//生成鄰接表 }solve();}return 0; }

對(duì)了，牛客網(wǎng)和poj的這個(gè)題都不支持頭文件，否則編譯錯(cuò)誤

總結(jié)

以上是生活随笔為你收集整理的The Bottom of a Graph Poj 2553的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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