LA 4287 Proving Equivalences / 强连通分量

给你一些命题 求最小还需要几次可以证明所有的命题都等价

一个强连通分量里面的题目都是等价的 只需缩点后 对于DAG图 入读为0和出度为0的点 两者之中最大值就是答案

如果只有1个强连通分量 那么无需证明了

#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
const int maxn = 20010;
vector <int> G[maxn];
stack <int> s;
int pre[maxn];
int low[maxn];
int sccno[maxn];//每个点所在强联通分量的scc_cnt 
int in[maxn];//每个强联通分量的入度 
int out[maxn];//每个强联通分量的出度
int dfs_clock;
int scc_cnt;
int n, m;

void dfs(int u)
{
	pre[u] = low[u] = ++dfs_clock;
	s.push(u);
	for(int i = 0; i < G[u].size(); i++)
	{
		int v = G[u][i];
		if(!pre[v])
		{
			dfs(v);
			low[u] = min(low[u], low[v]);
		}
		else if(!sccno[v])
		{
			low[u] = min(low[u], pre[v]);
		}
	}
	if(low[u] == pre[u])
	{
		scc_cnt++;
		while(1)
		{
			int x = s.top();
			s.pop();
			sccno[x] = scc_cnt;
			if(x == u)
				break;
		}
	}
}
void find_scc()
{
	dfs_clock = scc_cnt = 0;
	memset(sccno, 0, sizeof(sccno));
	memset(pre, 0, sizeof(pre));
	for(int i = 0; i < n; i++)
		if(!pre[i])
			dfs(i);
	
}
int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d %d", &n, &m);
		for(int i = 0; i < n; i++)
			G[i].clear();
		for(int i = 0; i < m; i++)
		{
			int u, v;
			scanf("%d %d", &u, &v);
			G[--u].push_back(--v);
		}
		find_scc();
		for(int i = 1; i <= scc_cnt; i++)
			in[i] = out[i] = 1;
		for(int u = 0; u < n; u++)
		{
			for(int i = 0; i < G[u].size(); i++)
			{
				int v = G[u][i];
				if(sccno[u] != sccno[v])
				{
					in[sccno[v]] = out[sccno[u]] = 0;
				}
			}
		}
		int a = 0, b = 0;
		for(int i = 1; i <= scc_cnt; i++)	
		{
			if(in[i])
				a++;
			if(out[i])
				b++;
		}
		int ans = max(a, b);
		if(scc_cnt == 1)
			ans = 0;
		printf("%d\n", ans);
	}
	return 0;
}

LA 4287 Proving Equivalences / 强连通分量

原文：http://blog.csdn.net/u011686226/article/details/18767747