割点.cpp

求有向图的强连通分量

// Cutvertex :

int N, edg[128][128], cnt[128];
int color, ti, cutvertexnum, cutvertexlist[MAXN];
int vis[MAXN], d[MAXN], low[MAXN];


void dfsvisit(int u, int p)
{
	int i, v, s=0, bVertex=0;
	low[u] = d[u] = ++ti;
	vis[u] = -color;
	for(i=0; i<cnt[u]; ++i)
	{
		v = edg[u][i];
		if(v==u) continue;
		if(!vis[v]) 
		{
			++s;
			dfsvisit(v,u);
			if(low[v] < low[u])
				low[u] = low[v];
			if(low[v] >= d[u])
				bVertex = 1;
		}
		else
			if(d[v] < low[u])
				low[u] = d[v];
	}
	if((p&&bVertex) || (!p&&s>1))
		cutvertexlist[cutvertexnum++] = u;
}

void dfs()
{
	int i, u;

	memset(vis, 0, sizeof(vis));
	color = cutvertexnum = ti = 0;

	for(u=1; u<=N; ++u)
		if(!vis[u])
		{
			++color;
			dfsvisit(u,0);
		}
	cout << cutvertexnum << endl;
	for(i=0; i<cutvertexnum; ++i)
		cout << cutvertexlist[i] << " ";
	cout << endl;
}