HDU 1269 迷宫城堡【Tarjan】

tonyfang posted @ 2016年8月12日 23:14 in HDU with tags C++ OI , 272 阅读

明天又要写题啦!

赶紧复习复习tarjan写个板子先。

HDU 1269 tarjan模板题

 

# include <stdio.h>
# include <string.h>
# include <algorithm>

using namespace std;


int tot=0, head[666666], Next[666666], to[666666];
int dfn[666666], low[666666];
int st[666666], stn=0, DFN=0;
bool ins[666666];
int belong[666666], nn=0;
int n, m;

inline void add(int u, int v) {
	++tot;
	Next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

inline void dfs(int x) {
	dfn[x] = low[x] = ++DFN;
	st[++stn] = x;
	ins[x] = 1;
	for (int i=head[x]; i; i=Next[i]) {
		if(!dfn[to[i]]) {
			dfs(to[i]);
			low[x] = min(low[x], low[to[i]]);
		} else if (ins[to[i]]) low[x] = min(low[x], dfn[to[i]]);
	}
	if(dfn[x] == low[x]) {
		++nn;
		while(stn && st[stn] != x) {
			belong[st[stn]] = nn;
			ins[st[stn]] = 0;
			--stn;
		}
		belong[st[stn]] = nn;
		ins[st[stn]] = 0;
		stn--;
	}
}
int main() {
	while(1) {
		scanf("%d%d", &n, &m);
		if(n==0 && m==0) break;
		memset(head, 0, sizeof(head));
		memset(dfn, 0, sizeof(dfn));
		memset(low, 0, sizeof(low));
		stn=0; nn=0, DFN=0, tot=0;
		memset(ins, 0, sizeof(ins));
		memset(belong, 0, sizeof(belong));
		for (int i=1, u, v; i<=m; ++i) {
			scanf("%d%d", &u, &v);
			add(u, v);
			//add(v, u);
		}
	
		for (int i=1; i<=n; ++i) {
			if(!dfn[i]) dfs(i);
		}
		/*
		for (int i=1; i<=n; ++i) printf("belong[%d]=%d\n", i, belong[i]);
		*/
		if(nn == 1) puts("Yes");
		else puts("No");
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter