hdu3594 Cactus

仙人掌入门简单题。

先看一篇文档。
#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int T, n, uu, vv, hea[20005], cnt, dfn[20005], loo[20005], idx, vis[20005];

bool isok;

struct Edge{

	int too, nxt;

}edge[50005];

void add_edge(int fro, int too){

	edge[++cnt].nxt = hea[fro];

	edge[cnt].too = too;

	hea[fro] = cnt;

}

void dfs(int x){

	if(!isok)	return ;

	dfn[x] = loo[x] = ++idx;

	vis[x] = 1;

	int num=0;

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(vis[t]==2)	isok = false;//1

		else if(!vis[t]){

			dfs(t);

			if(loo[t]>dfn[x])	isok = false;//2

			if(loo[t]<dfn[x]){//3

				num++;

				loo[x] = min(loo[x], loo[t]);

			}

		}

		else{//3

			loo[x] = min(loo[x], dfn[t]);

			num++;

		}

	}

	vis[x] = 2;

	if(num>1)	isok = false;

}

int main(){

	cin>>T;

	while(T--){

		scanf("%d", &n);

		memset(dfn, 0, sizeof(dfn));

		memset(loo, 0, sizeof(loo));

		memset(hea, 0, sizeof(hea));

		memset(vis, 0, sizeof(vis));

		isok = true;

		cnt = idx = 0;

		while(scanf("%d %d", &uu, &vv)!=EOF){

			if(!uu && !vv)	break;

			add_edge(uu+1, vv+1);

		}

		dfs(1);

		if(idx<n)	isok = false;

		printf(isok?"YES\n":"NO\n");

	}

	return 0;

}
巴特西

hdu3594 Cactus

最新文章

热门文章
