Graph_Master(连通分量_H_Trajan+拓扑序dp)

Graph_Master_连通分量_H

题目描述：　一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：?u,v∈V，满足u→v或v→u，即对于图中任意两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。若G'=(V',E')满足V'?V，E'是E中所有跟V'有关的边，则称G'是G的一个导出子图。若G'是G的导出子图，且G'半连通，则称G'为G的半连通子图。若G'是G所有半连通子图中包含节点数最多的，则称G'是G的最大半连通子图。给定一个有向图G，请求出G的最大半连通子图拥有的节点数K，以及不同的最大半连通子图的数目C。由于C可能比较大，仅要求输出C对X的余数。

题解：拿到题目是懵的，这个题目要我做什么玩意？？后来去翻了翻演算法，导出子图的意思就是拿出一些点，并且保留这些点之间所有的边，然后我就明白了，这题就是要Tarjan缩完点之后，找出拥有最多点的路径，并且求出有几条这样的路径。好了，Tarjan已经打到很熟练了，而且还是这种缩点的Tarjan。问题就转化成了如何找出拥有最多节点的路径，以及这种路径的数量。百度之后发现有个东西叫拓扑序dp？？我是谁？我怎么从来没有听说过？行吧，那就学吧，发现就是一个很简单的dp，一边做拓扑序的时候一边把dp做了，说是dp，其实更像是一个递推，过程挺好理解的，写起来难度也不大。

坑点：我个人觉得这题的数据有点奇怪，因为我自己打的代码是没有if used[v] == cur then continue 以及 used[v] = cur。因为我想到，既然缩点了，而且rebuild过程也是符合我的直观判断，及不会出现重边，但是这样交上去WA了，于是乎我百度到了别人的AC代码，就差了这个部分，可以说是很难受了，题目是下午A的，但是到现在也没有思路为啥要多个used，希望如果哪位看官看出了问题所在，能够告知一下我。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <vector>

#include <queue>

#define clr(a,b) memset(a,b,sizeof(a))

using namespace std;

const int M = 1e6 + 16;

const int N = 1e5 + 16;

struct Edge

{

	int u, v, nxt;

};

Edge edge[M];

int low[N], dfn[N], sta[N], col[N];

bool vis[N];

int dep, top, sum;

vector<int> son[N];

int n, m, X;

int head[N], ecnt;

void _add( int u, int v )

{

	edge[ecnt].u = u;

	edge[ecnt].v = v;

	edge[ecnt].nxt = head[u];

	head[u] = ecnt ++;

}

void tarjan( int u )

{

	low[u] = dfn[u] = ++dep;

	sta[++top] = u;

	vis[u] = 1;

	for ( int i = head[u]; i+1; i = edge[i].nxt )

	{

		int v = edge[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] )

	{

		col[u] = ++sum;

		vis[u] = 0;

		while ( sta[top] != u )

		{

			col[sta[top]] = sum;

			vis[sta[top--]] = 0;

		}

		top --;

	}

}

int in[N];

void rebuild()

{

	for ( int i = 1; i <= n; i ++ )

	{

		for ( int j = head[i]; j+1; j = edge[j].nxt )

		{

			int v = edge[j].v;

			if ( col[v] != col[i] )

			{

				son[col[i]].push_back(col[v]);

				in[col[v]] ++;

			}

		}

	}

}

void init()

{

	ecnt = top = sum = dep = 0;

	clr(head,-1);

	clr(dfn,0);

	clr(sta,0);

	clr(col,0);

	clr(vis,0);

	for ( int i = 0; i <= n; i ++ )

		son[i].clear();

}

int f[N], g[N];

int val[N];

int used[N];

void tp()

{

	queue<int> q;

	for ( int i = 1; i <= sum; i ++ )

	{

		if ( in[i] == 0 )

			q.push(i);

		f[i] = val[i], g[i] = 1;

	}

	while ( !q.empty() )

	{

		int cur = q.front(); q.pop();

		for ( int i = 0; i < son[cur].size(); i ++ )

		{

			int v = son[cur][i];

			in[v] --;

			if ( in[v] == 0 )

				q.push(v);

			if ( used[v] == cur ) continue;

			if ( f[cur] + val[v] > f[v] )

			{

				f[v] = f[cur] + val[v];

				g[v] = g[cur];

			}

			else if ( f[cur] + val[v] == f[v] )

				g[v] = ( g[v] + g[cur] ) % X;

			used[v] = cur;

		}

	}

}

int main()

{

	init();

	scanf("%d%d%d", &n, &m, &X );

	for ( int i = 0; i < m; i ++ )

	{

		int u, v;

		scanf("%d%d", &u, &v);

		_add(u,v);

	}

	for ( int i = 1; i <= n; i ++ )

		if ( !dfn[i] )

			tarjan(i);

	rebuild();

	for ( int i = 1; i <= n; i ++ )

		val[col[i]] ++;

	tp();

	int ans1, ans2;

	ans1 = ans2 = 0;

	for ( int i = 1; i <= sum; i ++ )

	{

		if ( f[i] > ans1 )

			ans1 = f[i], ans2 = g[i];

		else if ( f[i] == ans1 )

			ans2 = ( ans2 + g[i] ) % X;

	}

	printf("%d\n%d\n", ans1, ans2);

	return 0;

}

巴特西

Graph_Master(连通分量_H_Trajan+拓扑序dp)

最新文章

热门文章