HDU 1269 迷宫城堡【Tarjan】

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

明天又要写题啦!

赶紧复习复习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;
}
10thmodelpaper2020.i 说:
2023年4月18日 18:39

10th Board Model Paper 2023 Aspirants who had Registered for the Board 10th Class Exam can Download the Previous Paper When Board Announces the Dates to Download the Question Paper. 10thmodelpaper2020.in Board Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding the Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Model Paper.


登录 *


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