有向图——强连通分量

    有向图的强连通分量(strongly connected components)

在有向图G中，如果两个顶点vi,vj间(vi!=vj)有一条从vi到vj的路径，同时还有一条从vj到vi的路径(顶点相互可达)，则称两个顶点强连通。如果有向图G的每对顶点都强连通，称G是个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量。

    求解强连通分量的算法主要有三种：Kosaraju，Tarjan，Gabow。下面介绍Tarjan算法。

    Tarjan算法基于图的深度遍历。定义dfn[u]是结点u的时间戳，low[u]为u和u的子树能够追溯到的最早的栈中结点的时间戳。

    low[u] = min{dfn[u], low[v](u,v为树枝边，u为v的父节点), dfn[v](u,v为指向栈中结点的后向边)}；

    当dfn[u] == low[u]时，以u为根的搜索子树上所有结点是一个强连通分量。

 

关于Tarjan算法的详细介绍，参考:

http://hi.baidu.com/escorter2009/blog/item/f35951dc5bdb3de677c63826.html

 

POJ2186

题目大意：有n头牛，每头牛都希望自己受欢迎，输入a b表示a认为b受欢迎。要求出受其它所有牛欢迎的牛的个数。

解：首先求强连通分量，分量中每头牛都受分量中其它牛的欢迎。分量之间至多有一条有向边。那么显然需要找出出度为0的强连通分量，若有大于1的出度为0的强连通分量，这两个连通分量互相不认为对方受欢迎，显然个数为0；则有且仅有一个入读度为0的强连通分量时，该强连通分量的结点数即为解。

//出度为0的scc
#include <iostream>
const int MAX = 10002;
int n,m;
int low[MAX],dfn[MAX],seq;
bool inStack[MAX];
struct Edge
{
	int to;
	int next;
}e[50001];
int index[MAX],edgeNum;
int stack[MAX],top;
int belong[MAX];					//belong[i]表示结点i属于的连通分量
int outdegree[MAX];	
int cnt;							//cnt为当前强连通分量的标记值

int min(int x, int y)
{
	return x < y ? x : y;
}

void addEdge(int from, int to)
{
	e[edgeNum].to = to;
	e[edgeNum].next = index[from];
	index[from] = edgeNum++;
}

void Tarjan(int u)
{
	low[u] = dfn[u] = seq++;
	stack[top++] = u;						//将结点u入栈
	inStack[u] = true;
	for(int i = index[u]; i != -1; i = e[i].next)
	{
		int w = e[i].to;
		if(dfn[w] < 0)
		{
			Tarjan(w);
			low[u] = min(low[u],low[w]);
		}
		else if(inStack[w])					//如果节点w还在栈内
			low[u] = min(low[u],dfn[w]);
	}
	if(dfn[u] == low[u])				//u是强连通分量的根
	{
		int v;
		cnt++;
		//出栈，缩点
		do
		{
			top--;
			v = stack[top];
			inStack[v] = false;
			belong[v] = cnt;
		}while(u != v);
	}
}

void solve()
{
	int i,j;
	for(i = 1; i <= n; i++)
		if(dfn[i] < 0)
			Tarjan(i);
	for(i = 1; i <= n; i++)
	{
		for(j = index[i]; j != -1; j = e[j].next)
		{
			if(belong[i] != belong[e[j].to])
				outdegree[belong[i]]++;
		}
	}
	int num = 0;	//出度为0的连通分量的个数
	int who;		//哪个连通分量
	for(i = 1; i <= cnt; i++)
	{
		if(outdegree[i] == 0)
		{
			who = i;
			num++;
		}
	}
	if(num != 1)
		printf("0\n");
	else
	{
		int result = 0;
		for(i = 1; i <= n; i++)
			if(belong[i]==who)
				result++;
		printf("%d\n",result);
	}
}

int main()
{
	int i,j;
	int from,to;
	edgeNum = 0;
	seq = 0;
	top = 0;
	cnt = 0;
	memset(dfn,-1,sizeof(dfn));
	memset(index,-1,sizeof(index));
	memset(inStack,0,sizeof(inStack));
	memset(outdegree,0,sizeof(outdegree));
	scanf("%d %d",&n,&m);
	for(i = 0; i < m; i++)
	{
		scanf("%d %d",&from,&to);
		addEdge(from,to);
	}
	solve();
	return 0;
}

 

POJ2553

题目大意：一个图由结点集v和边集E组成，现在要求出一个点集合：

    bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}(对于集合中的任意一点v和V中的任意一点w，如果v能到达w，那么w也能到达v)。

解：首先求强连通分量，联想到出度为0的scc(因为出度不为0的scc，不满足集合的定义)。

//出度为0的所有scc
#include <iostream>
const int MAX = 5005;
int n,m;

struct Edge
{
	int to;
	int next;
}e[MAX*MAX];
int index[MAX],edgeNum;

int low[MAX],dfn[MAX],seq;
int stack[MAX],top;
bool inStack[MAX];
int belong[MAX],outdegree[MAX],cnt;
int result[MAX],count;

int min(int x, int y)
{
	return x < y ? x : y;
}

void addEdge(int from, int to)
{
	e[edgeNum].to = to;
	e[edgeNum].next = index[from];
	index[from] = edgeNum++;
}

void Tarjan(int u)
{
	low[u] = dfn[u] = seq++;
	stack[top++] = u;
	inStack[u] = true;
	for(int i = index[u]; i != -1; i = e[i].next)
	{
		int w = e[i].to;
		if(dfn[w] < 0)
		{
			Tarjan(w);
			low[u] = min(low[u],low[w]);
		}
		else if(inStack[w])					//如果节点w还在栈内
			low[u] = min(low[u],dfn[w]);
	}
	if(low[u] == dfn[u])
	{
		int v;
		cnt++;
		do
		{
			top--;
			v = stack[top];
			inStack[v] = false;
			belong[v] = cnt;
		}while(u != v);
	}
}

void solve()
{
	int i,j;
	for(i = 1; i <= n; i++)
		if(dfn[i] < 0)
			Tarjan(i);
	for(i = 1; i <= n; i++)
	{
		for(j = index[i]; j != -1; j = e[j].next)
		{
			if(belong[i] != belong[e[j].to])
				outdegree[belong[i]]++;
		}
	}
	for(i = 1; i <= n; i++)
	{
		if(outdegree[belong[i]] == 0)
			result[count++] = i;
	}
}

int main()
{
	int i,j;
	int from,to;
	while(true)
	{
		scanf("%d",&n);
		if(n==0)
			break;
		edgeNum = top = seq = count = cnt =0;
		memset(dfn,-1,sizeof(dfn));
		memset(index,-1,sizeof(index));
		memset(inStack,0,sizeof(inStack));
		memset(belong,0,sizeof(belong));
		memset(outdegree,0,sizeof(outdegree));
		scanf("%d",&m);
		for(i = 0; i < m; i++)
		{
			scanf("%d %d",&from,&to);
			addEdge(from,to);
		}
		solve();
		if(count == 0)
			printf("\n");
		else
		{
			for(i = 0; i < count-1; i++)
				printf("%d ",result[i]);
			printf("%d\n",result[i]);
		}
	}
	return 0;
}