首页 > 代码库 > 【POJ1236】Network of Schools 强联通分量缩点(本文kosaraju)

【POJ1236】Network of Schools 强联通分量缩点(本文kosaraju)

/*不要说这题多水之类的……我只是想记一下kosaraju这种屌炸天的dfs序延伸算法(说不定能加到我的ygylca里面)*/

题意神马的都不说了,好吧,就是给你个图,n个点,然后n行每行都描述该点的出边,图建完了,然后缩点,然后问多少个点没有入度,再问需要加几条边可以让图变强联通图。


强联通图:图中任意两点之间都能互相到达(前提得是有向图你懂的,无向图就有点乱了,根本不要算法了,暴搜就好了)

强联通分量:同强联通图,不过是图中一部分。

缩点,把一个分量视为一个点,缩起来(一般不缩,都是记录每个点在第几个强联通分量里)


kosaraju算法:这厮乃印度人氏也,算法名之甚屌!算法:正着搜一遍,当出边都跑完时记录其dfn[x]=++cnt;然后反向建图(一般在开始就建好),再根据dfn序n-->1在反向图上跑一遍dfs,能扫到且没被赋值(未分配分量序号)的点都是一个同一个强联通分量里的。


(各种“联通”“连通”我就不管了,别吐槽,好像是连通吧?)


两种代码

一种是邻接矩阵,就是存个bool map[maxn][maxn]表示能不能通,然后不用建反图。

另一种就是邻接表(链式前向星)了,需要建反图,而且这道题可能是稠密图,所以不建议。

当然,我二分提交了十多遍代码,测出最多有2477条边,用邻接表时可以参考一下。

先不着急贴代码,先写一下我对kosaraju的理解性证明,当然,可能有点不严谨,不乐意看的可以去看这篇博客,写得好像很不错(我是看着有点蒙(没耐心,虽然很短)):

http://blog.csdn.net/dm_vincent/article/details/8554244

好了,说一下我的证明

先说一下各种变量的含义:

struct KSD
{
int v,next;
}ea[M],eb[M];/*正图,反图*/
int heada[N],headb[N],num,n;/*head数组不说了*/
int dfn[N],cnt;/*dfn可以参照代码*/
int id[N],group;/*id[i],i在第几个强联通分量里*/
int rd[N],od[N];/*入度出度*/
bool visit[N];/*正图dfs时是否被扫过*/


首先我们在反图上dfs时,扫到即同分量,即在扫i点时,所有能到i点且未赋id的点(包括i点)都是一个强联通分量,我们从这里证起。

若a点和i点强联通,那么可以肯定若b点同样和i点强联通,那么a和b强联通吧?这个很好理解,.水水的.!那么我们只对这个分量里每个点都和i点强联通就好了。

强联通:a能到i,i也能到a。

既然能扫到,那么可以确定a能到i,没异议吧?有异议就想到没异议再往下看。现在我们只需要证明i能到a了!

若dfn[a]>dfn[i],则a肯定有id值了,对吧?那么肯定不能再有i->a了。所以此时我们可以穷举所有的情况。

首先我们dfs时实际上建立了一颗搜索树,我们可以举两种情况,① a在i的子树里。② a不在i的子树里。

先说①。这个i肯定能搜到a没问题吧?(a就是由i搜过去的!)

再说一下②,两种情况:②-①若i在a的子树里,没扫完i给i赋完id值,a是绝对不会赋id值的对吧?那么就矛盾于一行了,那么就有②-②i就一定不能在a的子树里面。所以又可以分为两种情况。

②-②-①在他们的lca时,先扫到i分支。②-②-②先扫到a分支。

先说②-②-①:既然扫到了i分支,那么如果i能到a,则因为扫到i时a一定还没被扫过,所以可以从i去扫a,那么就跟前置命题“②-②”矛盾,因为此时a竟然成了i的祖先?!!命题为假。

再说②-②-②:同②-②-①,从i不可以扫到a,否则矛盾于“②”,所以i到不了a。

quit,to②-②(因为两种命题都是false),所以quit,to②,②又是false。


所以可以肯定只有a在i子树里面,才可以使得强联通分量成立!

证毕!

codes:

邻接矩阵:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 105
using namespace std;
//kosaruju算法! 
int n;
int dfn[N],cnt;
int id[N],group;
int rd[N],od[N];
bool map[N][N],visit[N];

int ans1,ans2;

void init()
{
	cnt=group=0;
	ans1=ans2=0;
	memset(map,0,sizeof(map));
	memset(visit,0,sizeof(visit));
	memset(id,0,sizeof(id));
	memset(rd,0,sizeof(rd));
	memset(od,0,sizeof(od));
}

void dfs(int x)
{
	visit[x]=1;
	for(int i=1;i<=n;i++)if(map[x][i]&&!visit[i])dfs(i);
	dfn[++cnt]=x;
	return ;
}
void dfst(int x)
{
	id[x]=group;
	for(int i=1;i<=n;i++)if(map[i][x]&&!id[i])dfst(i);
	return ;
}

void kosaruju()
{
	int i,j,v;
	for(i=1;i<=n;i++)if(!visit[i])dfs(i);
	for(i=n;i;i--)
	{
		v=dfn[i];
		if(!id[v])
		{
			group++;
			dfst(v);
		}
	}
	return ;
}
void handle()
{
	int i,j,u,v;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			u=id[i];
			v=id[j];
			if(map[i][j]&&u!=v)
			{
				od[u]++;
				rd[v]++;
			}
		}
	}
	for(i=1;i<=group;i++)
	{
		if(!rd[i])ans1++;
		if(!od[i])ans2++;
	}
/*	if(group==1)ans2=0;
	加上这句没有任何用的废话就可以0ms(别忘了删注释)
	我猜可能是编译时发生了某未知影响,并进而影响了评测时间。
	run id:poj 13468874
*/	printf("%d\n",ans1);
	if(group==1)puts("0");
	else printf("%d\n",max(ans1,ans2));
}

int main()
{
//	freopen("test.in","r",stdin);
	int i,a;
	while(scanf("%d",&n)!=EOF)
	{
		init();
		for(i=1;i<=n;i++)while(scanf("%d",&a),a)map[i][a]=1;
		kosaruju();
		handle();
	}
	return 0;
}

邻接表(链式前向星):

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 105
#define M 2477/*极限数据2477条边,但是正常应该开10010(甚至因为它没说有没有重边,还应该开更大!)*/
using namespace std;
//kosaruju算法!
struct KSD
{
	int v,next;
}ea[M],eb[M];
int heada[N],headb[N],num,n;
int dfn[N],cnt;
int id[N],group;
int rd[N],od[N];
bool visit[N];
int ans1,ans2;

void add(int u,int v)
{
	++num;
	ea[num].v=v;
	eb[num].v=u;
	ea[num].next=heada[u];
	eb[num].next=headb[v];
	heada[u]=headb[v]=num;
}

void init()
{
	ans1=ans2=0;
	num=cnt=group=0;
	memset(id,0,sizeof(id));
	memset(rd,0,sizeof(rd));
	memset(od,0,sizeof(od));
	memset(heada,0,sizeof(heada));
	memset(headb,0,sizeof(headb));
	memset(visit,0,sizeof(visit));
}

void dfs(int x)
{
	int i,v;
	visit[x]=1;
	for(i=heada[x];i;i=ea[i].next)
	{
		v=ea[i].v;
		if(!visit[v])dfs(v);
	}
	dfn[++cnt]=x;
}
void dfst(int x)
{
	int i,v;
	id[x]=group;
	for(i=headb[x];i;i=eb[i].next)
	{
		v=eb[i].v;
		if(!id[v])dfst(v);
	}
}

void kosaruju()
{
	int i,j,v;
	for(i=1;i<=n;i++)if(!visit[i])dfs(i);
	for(i=n;i;i--)
	{
		v=dfn[i];
		if(!id[v])
		{
			group++;
			dfst(v);
		}
	}
	return ;
}
void handle()
{
	int i,j,u,v;
	for(i=1;i<=n;i++)
	{
		u=id[i];
		for(j=heada[i];j;j=ea[j].next)
		{
			v=id[ea[j].v];
			if(u!=v)
			{
				od[u]++;
				rd[v]++;
			}
		}
	}
	for(i=1;i<=group;i++)
	{
		if(!rd[i])ans1++;
		if(!od[i])ans2++;
	}
/*	if(group==1)ans2=0;
	加上这句没有任何用的废话就可以0ms(别忘了删注释)
	我猜可能是编译时发生了某未知影响,并进而影响了评测时间。
	run id:poj 13468874
*/	printf("%d\n",ans1);
	if(group==1)puts("0");
	else printf("%d\n",max(ans1,ans2));
}

int main()
{
//	freopen("test.in","r",stdin);
	int i,a;
	while(scanf("%d",&n)!=EOF)
	{
		init();
		for(i=1;i<=n;i++)while(scanf("%d",&a),a)add(i,a);
		kosaruju();
		handle();
	}
	return 0;
}





复制去Google翻译翻译结果
代码

【POJ1236】Network of Schools 强联通分量缩点(本文kosaraju)