POJ 2553 The Bottom of a Graph TarJan算法題解

本題分兩步：

1 使用Tarjan算法求所有最大子強連通圖，並且標志出來

2 然後遍歷這些節點看是否有出射的邊，沒有的頂點所在的子強連通圖的所有點，都是解集。

Tarjan算法就是模板算法了。

這裡使用一個數組和一個標識號，就可以記錄這個頂點是屬於哪個子強連通圖的了。

然後使用DFS遞歸搜索所有點及其邊，如果有邊的另一個頂點不屬於本子強連通圖，那麼就說明有出射的邊。

有難度的題目：

#include 
#include 
#include 
#include 
using namespace std;

const int MAX_VEC = 5005;
int n, m;
vector gra[MAX_VEC];
stack stk;
int dfn[MAX_VEC];//tarjan算法記錄深度探索得到的標號
int low[MAX_VEC];//tarjan算法記錄回溯得到的最低頂點編號
bool inStk[MAX_VEC];//記錄是否在棧裡面，也可以記錄是否被訪問過了
int connectGrp[MAX_VEC];//標志所屬的連通子圖標號 == connectNum
int vecNum;//頂點標號
int connectNum;//最大強連通子圖標號
int out[MAX_VEC];//出度記錄

void tarjan(int u)
{
	dfn[u] = low[u] = vecNum++;
	stk.push(u);
	inStk[u] = 1;
	for (int i = 0; i < (int)gra[u].size(); i++)
	{
		int v = gra[u][i];
		if (!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);//兩處的不同，和含義不同
		}
		else if (inStk[v]) low[u] = min(dfn[v], low[u]);//兩處的不同
	}
	if (low[u] == dfn[u])
	{
		++connectNum;
		while (stk.size())
		{
			int v = stk.top(); stk.pop();
			inStk[v] = false;
			connectGrp[v] = connectNum;
			if (u == v) return;
		}
	}
}

void solveConnect()
{
	memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low));
	memset(inStk, 0, sizeof(inStk));
	for (int i = 1; i <= n; i++)
	{
		if (!dfn[i]) tarjan(i);
	}
}

void dfsCountOut(int u)
{
	inStk[u] = true;	//記錄是否被訪問過了
	for (int i = 0; i < int(gra[u].size()); i++)
	{
		int v = gra[u][i];
		if (connectGrp[u] != connectGrp[v])
		{
			out[connectGrp[u]]++;//這個組的出度增加; connectGrp[] == connectNum
		}
		if (!inStk[v]) dfsCountOut(v);//深度優先，不需要使用額外空間
	}
}

void countConnectOut()
{
	memset(inStk, 0, sizeof(inStk));	//這裡只記錄是否被訪問過的了。
	memset(out, 0, sizeof(out));
	for (int i = 1; i <= n; i++)
	{
		if (!inStk[i]) dfsCountOut(i);
	}
}

int main()
{
	int u, v;
	while (scanf("%d", &n) && n)
	{
		connectNum = 0;
		vecNum = 1;
		scanf("%d", &m);
		for (int i = 1; i <= n; i++)
			gra[i].clear();
		while (stk.size()) stk.pop();	//清零，重中之重

		for (int i = 0; i < m; i++)
		{
			scanf("%d %d", &u, &v);
			gra[u].push_back(v);	//有向圖
		}

		solveConnect();
		countConnectOut();

		for(int i = 1; i <= n; ++i)
			if(out[connectGrp[i]] == 0)
				printf("%d ", i);
		putchar('\n');
	}
	return 0;
}