POJ--2553 图的底部

题目描述

输入样例

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

输出样例

1 3
2

思路

算法设计

参考代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn = 5050;
int n, m;
bool ins[maxn];//标记是否在栈内 
int head[maxn], belong[maxn], out[maxn];//belong:标记连通分量, out:出度. 
int low[maxn], dfn[maxn];
stack<int>s;
int cnt, num, id;
struct Egde
{
   
	int to, next;
}e[maxn << 1];
void add(int u, int v)
{
   
	e[++cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}
void init()
{
   
	memset(head, 0, sizeof(head));
	memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low));
	memset(ins, false, sizeof(ins));
	memset(out, 0, sizeof(out));
	memset(belong, 0, sizeof(belong));
	cnt = 0;
	num = 0;
	id = 1;
}

void tarjan(int u)
{
   
	low[u] = dfn[u] = ++num;//开始访问
	ins[u] = true;// 标记是否在栈里
	s.push(u);
	for (int i = head[u]; i; i = e[i].next)
	{
   
		int v = e[i].to;
		if (!dfn[v])
		{
   
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (ins[v]) {
   //如果已经访问过
			low[u] = min(low[u], low[v]);
		}

	}
	if (low[u] == dfn[u]) {
   
		int v;
		do {
   
			v = s.top();
			s.pop();
			belong[v] = id;//标记连通分量
			ins[v] = false;//节点出栈,修改标记
		} while (v != u);
		id++;
	}
}

int main()
{
   
	while ((cin>>n)&&n)
	{
   
		cin >> m;
		init();
		while (m--)
		{
   
			int u, v;
			cin >> u >> v;
			add(u, v);

		}
		for (int i = 1; i <= n; i++) {
   
			if (!dfn[i])
				tarjan(i);
		}
		for (int u = 1; u <= n; u++)//遍历每个节点,标记每个连通分量的出度
		{
   
			for (int i = head[u]; i ; i = e[i].next)
			{
   
				int v = e[i].to;
				if (belong[u] != belong[v]) {
   //如果u和v连通分量号不同
					out[belong[u]]++;//u节点所在连通分量号的出度++. 用连通分量号来指代连通分量
				}
			}
			
		}
		int flag = 1;
		for (int i = 1; i <= n; i++)
		{
   
			if (!out[belong[i]]) {
   
				if (flag) {
   //第一个数据前面没有空格,之后每个以空格分隔.
					flag = 0;
				}
				else {
   
					cout << " ";
				}
				cout << i;
			}
		}
		cout << endl;
	}
	return 0;
}