UVa11324 - The Largest Clique

Online Judge

题目大意：有一张n个点m条边的图，现对于每一个点u，建立一条边连接它和所有它能到达的点，问满足所有点之间都有边的分量的大小最大是多少

0<=n<=1000;0<=m<=50000

思路：根据建新图的规则可知，一个点会和它能到达的所有点构成一个合法的分量，那么从入度为0的点开始组成的这样一个分量一定是最大的，但是因为图中有环，所以没法直接统计这样的分量的大小，所以要先用tarjan将所有强量通分量缩成一个点，再在新图中用记忆化搜索找上述的分量

//#include<__msvc_all_public_headers.hpp>
#include
using namespace std;
const int N = 1e3 + 5;
int head[N], head2[N];
struct Edge
{
	int v, next;
}e[N * N], e2[N * N];
int dfn[N], low[N];
int c1 = 0, c2 = 0;
void addedge(int u, int v)
{//原图
	e[++c1].v = v;
	e[c1].next = head[u];
	head[u] = c1;
}
void addedge2(int u, int v)
{//缩点后的新图
	e2[++c2].v = v;
	e2[c2].next = head2[u];
	head2[u] = c2;
}
bool vis[N];
int cnt = 0;
int ans = 0;
stack<int>s;
int siz[N];
pair<int, int>edge[N * N];
int n, m;
int cnts[N];
int scc[N];
void tarjan(int u)
{//将图拆解成强连通分量的组合
	cnt++;//访问次序
	dfn[u] = low[u] = cnt;//每个点的访问次序，在第几个强连通分量里	
	s.push(u);//储存dfs中待处理的点
	vis[u] = 1;//在栈内待处理
	for (int i = head[u]; ~i; i=e[i].next)
	{
		int v = e[i].v;
		if (!dfn[v])
		{//子节点没被访问过
			tarjan(v);
			low[u] = min(low[u], low[v]);//和子节点合并成一个强连通分量
		}
		else if (vis[v])
		{//重复访问了栈内的节点
			low[u] = min(low[u], low[v]);//这两个点一定在一个强连通分量内
		}
	}
	if (dfn[u] == low[u])
	{//当前点是这个强连通分量的第一个点，也就是这个分量都已处理完毕
		int temp = 0;//记录强连通分量的点数
		ans++;//第几个强连通分量
		while (!s.empty() && s.top() != u)
		{//将这个强量通分量内的点全部弹出		
			vis[s.top()] = 0;//不在栈内
			scc[s.top()] = ans;//每个点属于哪个强连通分量
			temp++;
			s.pop();
		}
		temp++;
		vis[s.top()] = 0;//第一个点也要弹出
		scc[s.top()] = ans;
		s.pop();
		siz[ans] = temp;//这个连通块里面几个点
		
	}
}
int in[N];
void init()
{
	c1 = c2 = 0;
	for (int i = 1; i <= n; i++)
	{
		vis[i] = 0;
		dfn[i] = low[i] = siz[i] = 0;
		head[i] = head2[i] = -1;
		cnts[i] = 0;
		in[i] = 0;
	}
	while (!s.empty())
	{
		s.pop();
	}
	cnt = ans = 0;
}
int dfs(int u)
{//记忆化搜索能到达多少个点
	if (cnts[u])
	{
		return cnts[u];
	}
	int ma = 0;
	for (int i = head2[u]; ~i; i=e2[i].next)
	{
		int v = e2[i].v;
		ma = max(ma, dfs(v));//取子节点里面最大的
	}
	cnts[u] = siz[u] + ma;//这个歌两桶快的大小加子节点传来的值
	return cnts[u];
}
void solve()
{
	cin >> n >> m;
	init();
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		edge[i] = { u,v };
		addedge(u, v);
	}
	for (int i = 1; i <= n; i++)
	{
		if (!dfn[i])//所有没处理的点都要处理
			tarjan(i);
	}
	for (int i = 1; i <= m; i++)
	{
		int u = edge[i].first, v = edge[i].second;
		if (scc[u] != scc[v])
		{//两个点不在一个强连通分块里
			addedge2(scc[u], scc[v]);//建新图
			in[scc[v]]++;
		}
	}
	int out = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!in[i])
		{//从入度为0的点出发开始搜
			out = max(out, dfs(i));
		}
	}
	cout << out << '\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}