poj2553

maksyuki 发表于 oj 分类，标签: 图论-有向图强连通分量

23 1月 2016

The Bottom of a Graph

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=(e₁,...,e_n) be a sequence of length n of edges e_i∈E such that e_i=(v_i,v_i+1) for a sequence of vertices (v₁,...,v_n+1). Then p is called a path from vertex v₁ to vertex v_n+1 in G and we say that v_n+1 is reachable from v₁, writing (v₁→v_n+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 v₁,w₁,...,v_e,w_e with the meaning that (v_i,w_i)∈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

Source

Ulm Local 2003

题目类型：有向图强连通分量(Tarjan)+缩点

算法分析：本题要找所有满足”能够到达其他顶点w(w != u)的点u是否能够从w点到达”的所有的u点，即不考察那些u不可达的点的情况。由于同一个强连通分量中的顶点都是双向可达的，所以其中任意一个点对于同一个强连通分量中的其它点都是满足条件的，可以缩点。易知缩点后得到的图中出度为0的缩点都满足条件

/*************************************************
Author        :supermaker
Created Time  :2016/1/23 13:13:31
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 5000 + 66;

int dfn[maxn], low[maxn], belong[maxn], outdeg[maxn];
bool instack[maxn];
int n, m, id, tot;
vector <int> g[maxn], num[maxn], out;
stack <int> sta;

void dfs (int u)
{
	dfn[u] = low[u] = ++id;
	sta.push (u);
	instack[u] = true;
	for (int i = 0; i < g[u].size (); i++)
	{
		int v = g[u][i];
		if (!dfn[v])
		{
			dfs (v);
			low[u] = min (low[u], low[v]);
		}
		else if (instack[v])
			low[u] = min (low[u], dfn[v]);
	}
	
	if (low[u] == dfn[u])
	{
		tot++;
		int tt;
		do
		{
			tt = sta.top (); sta.pop ();
			instack[tt] = false;
			belong[tt] = tot;
			num[tot].push_back (tt);
		} while (!sta.empty () && tt != u);
	}
}

void SS ()
{
	memset (dfn, 0, sizeof (dfn));
	memset (low, 0, sizeof (low));
	memset (instack, false, sizeof (instack));
	id = tot = 0;
	while (!sta.empty ()) sta.pop ();
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			dfs (i);
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d", &n) != EOF)
	{
		if (n == 0) break;
		scanf ("%d", &m);
		for (int i = 0; i < maxn; i++)
			g[i].clear (), num[i].clear ();
		
		for (int i = 1; i <= m; i++)
		{
			int u, v;
			scanf ("%d%d", &u, &v);
			g[u].push_back (v);
		}
		SS ();
		memset (outdeg, 0, sizeof (outdeg));
		for (int u = 1; u <= n; u++)
			for (int i = 0; i < g[u].size (); i++)
			{
				int v = g[u][i];
				if (belong[u] != belong[v])
					outdeg[belong[u]]++;
			}
		out.clear ();
		for (int i = 1; i <= tot; i++)
			if (!outdeg[i])
			{
				for (int j = 0; j < num[i].size (); j++)
					out.push_back (num[i][j]);
			}
		
		sort (out.begin (), out.end ());
		for (int i = 0; i < out.size (); i++)
		{
			if (i == 0) printf ("%d", out[i]);
			else printf (" %d", out[i]);
		}
		puts ("");
	}
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

/*************************************************

Author :supermaker

Created Time :2016/1/23 13:13:31

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 5000 + 66;

int dfn[maxn], low[maxn], belong[maxn], outdeg[maxn];

bool instack[maxn];

int n, m, id, tot;

vector <int> g[maxn], num[maxn], out;

stack <int> sta;

void dfs (int u)

{

dfn[u] = low[u] = ++id;

sta.push (u);

instack[u] = true;

for (int i = 0; i < g[u].size (); i++)

{

int v = g[u][i];

if (!dfn[v])

{

dfs (v);

low[u] = min (low[u], low[v]);

}

else if (instack[v])

low[u] = min (low[u], dfn[v]);

}

if (low[u] == dfn[u])

{

tot++;

int tt;

{

tt = sta.top (); sta.pop ();

instack[tt] = false;

belong[tt] = tot;

num[tot].push_back (tt);

} while (!sta.empty () && tt != u);

}

void SS ()

{

memset (dfn, 0, sizeof (dfn));

memset (low, 0, sizeof (low));

memset (instack, false, sizeof (instack));

id = tot = 0;

while (!sta.empty ()) sta.pop ();

for (int i = 1; i <= n; i++)

if (!dfn[i])

dfs (i);

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d", &n) != EOF)

{

if (n == 0) break;

scanf ("%d", &m);

for (int i = 0; i < maxn; i++)

g[i].clear (), num[i].clear ();

for (int i = 1; i <= m; i++)

{

int u, v;

scanf ("%d%d", &u, &v);

g[u].push_back (v);

}

SS ();

memset (outdeg, 0, sizeof (outdeg));

for (int u = 1; u <= n; u++)

for (int i = 0; i < g[u].size (); i++)

{

int v = g[u][i];

if (belong[u] != belong[v])

outdeg[belong[u]]++;

}

out.clear ();

for (int i = 1; i <= tot; i++)

if (!outdeg[i])

{

for (int j = 0; j < num[i].size (); j++)

out.push_back (num[i][j]);

}

sort (out.begin (), out.end ());

for (int i = 0; i < out.size (); i++)

{

if (i == 0) printf ("%d", out[i]);

else printf (" %d", out[i]);

}

puts ("");

}

return 0;

}

poj2186

poj1236

超客的水墨烟雨

poj2553

分类目录

标签云

书签

近期评论

2024年4月
一	二	三	四	五	六	日
« 6月
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