汽车网站建设策划方案,郑州建站排名,目前it行业哪个方向前景最好,夹江企业网站建设报价Online Judge
题目大意#xff1a;有一张n个点m条边的图#xff0c;现对于每一个点u#xff0c;建立一条边连接它和所有它能到达的点#xff0c;问满足所有点之间都有边的分量的大小最大是多少
0n1000;0m50000
思路#xff1a;根据建新图的规则可知有一张n个点m条边的图现对于每一个点u建立一条边连接它和所有它能到达的点问满足所有点之间都有边的分量的大小最大是多少
0n1000;0m50000
思路根据建新图的规则可知一个点会和它能到达的所有点构成一个合法的分量那么从入度为0的点开始组成的这样一个分量一定是最大的但是因为图中有环所以没法直接统计这样的分量的大小所以要先用tarjan将所有强量通分量缩成一个点再在新图中用记忆化搜索找上述的分量
//#include__msvc_all_public_headers.hpp
#includebits/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;
stackints;
int siz[N];
pairint, intedge[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; ie[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; ie2[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;
}
