UVa11324 - The Largest Clique

Online Judge

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

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

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

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
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;
}