강력 한 연결 분량 - tarjan 알고리즘 이 그림 에서 의 응용 (1)

tarjan 알고리즘 은 다양한 도 론 문제 에서 광범 위 하 게 응용 되 고 있다.현재, 우 리 는 tarjan 알고리즘 이 그림 에 강 한 연결 분량 을 구 할 때 응용 하 는 것 에 대해 토론 합 니 다.
그림 이 없 는 절 점 을 구 하 는 것 과 마찬가지 로 우 리 는 dfs 와 low 두 개의 배열 을 사용 해 야 한다. 그 의 미 는 여기 서 더 이상 군말 하지 않 는 다.그 밖 에 우 리 는 보조 창고 로 배열 을 하나 더 열 어야 한다.
강 한 연결 을 구 하 는 사고 와 절단 점 도 비슷 하 다.우 리 는 그림 에 대해 dfs, dfs 배열 과 low 배열 의 구법 을 구 할 때 와 마찬가지 로 dfs 가 한 점 에 도착 할 때마다 이 를 이미 달 한 것 으로 표시 하고 스 택 에 넣 습 니 다.점 x 의 모든 아웃 사 이 드 를 옮 겨 다 닌 후에 dfs [x] = low [x] 가 있 으 면 x 와 스 택 에 있 는 모든 것 이 x 이상 의 점 에서 강 한 연결 분량 을 구성 하고 스 택 에서 나 온 다 는 것 을 설명 합 니 다.필요 하 다 면 염색 등 을 할 수 있다.증명 은 다음 과 같다. 만약 에 x 의 서브 트 리 에 x 를 포함 하지 않 는 강 한 연결 분량 이 포함 되 어 있다 면 x 를 뿌리 로 하 는 dfs 가 끝나 기 전에 이 강 한 연결 분량 은 반드시 팝 업 될 것 이다.
이렇게 해서 우 리 는 그림 에 강 한 연결 분량 을 구 해 냈 다.
인기 있 는 소 P2341
이 문제 에서 한 무리의 소 가 하나의 강 한 연결 분량 을 구성한다 면 그 중의 한 마리 가 스타 젖소 라면 이 젖소 가 있 는 강 한 연결 분량 중의 모든 젖 소 는 스타 젖소 이다.또 어떤 강 한 연결 분량 이 나 오 면 이 강 한 연결 분량 의 모든 젖소 가 스타 젖소 가 아니다.그리고 두 개 이상 의 강 한 연결 분량 의 출 도가 0 이면 스타 젖소 가 존재 하지 않 는 다.
강 한 연결 분량 의 출 도와 입 도 에 대해 우 리 는 특정한 강 한 연결 분량 을 스 택 에서 꺼 낼 때 이 를 염색 하여 모든 강 한 연결 분량 을 구 한 후에 우 리 는 모든 변 을 옮 겨 다 닐 수 있다. 만약 에 변 의 양쪽 색 이 일치 하지 않 으 면 출발점 이 있 는 강 한 연결 분량 의 출 도 + 를 주 고 마지막 에 이미 세 어 진 출입 도 를 옮 겨 다 니 며 판단 하면 된다.
AC 코드:

#include
#include
using namespace std;
int n,m,head[10005],ecnt=1,x,y,cnt=1,ans;
int dfn[10005],low[10005],v[10005];
int s[10005],dfsc,h,c[10005],out[10005],size[10005];
//v:vis s:stack dfsc:dfs  h:  
//c:color out:   cnt:       size:      
struct list{
	int r,n;
}l[50005];
void add(int a,int b)
{
	l[ecnt].r=b;
	l[ecnt].n=head[a];
	head[a]=ecnt++;
}
void pop(int x)
{
	int num=1;
	while(s[h-1]!=x)
	{
		num++;
		v[s[h-1]]=0;
		c[s[h-1]]=cnt;
		h--;
	}
	c[x]=cnt;
	h--;
	size[cnt++]=num;
}
void dfs(int x)
{
	low[x]=dfn[x]=++dfsc;
	s[h++]=x;
	v[x]=1;
	for(int i=head[x];i;i=l[i].n)
	{
		int p=l[i].r;
		if(!dfn[p])
		{
			dfs(p);
			low[x]=min(low[p],low[x]);
		}
		else low[x]=min(low[p],low[x]);
	}
	if(dfn[x]==low[x]) pop(x);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {scanf("%d%d",&x,&y);add(x,y);}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i]) dfs(i);
		else if(!dfn[i]) {printf("0");return 0;}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=head[i];j;j=l[j].n)
		{
			int p=l[j].r;
			if(c[p]!=c[i]) out[c[i]]++;
		}
	}
	for(int i=1;i<cnt;i++)
	{
		if(ans&&out[i]==0) {printf("0");return 0;}
		if(out[i]==0) ans=size[i];
	}
	printf("%d",ans);
	return 0;
}