TIOJ 1484 仙人掌 [Graph]

poao899    1484    Accepted    824K    947MS    G++    1.89K    2010-04-03 20:44:58                           .



可愛題。

給你一張圖問你是不是符合以下條件

1.  整張圖都在同一個SCC
2.  每條邊只能而且必須屬於一個而且只有一個簡單圈












先做一次SCC

之後作v次DFS拔邊，均攤O(E)


//******************************************

#include<stdio.h>
#define MAXV 100100
int T, n,  m, stamp, tt, a, b, cnt, eCnt, _tar;
int vst[MAXV], can;
struct edge{
	int i, j;
	edge *next;
	void set(int a, int b, edge **vv){
		edge *p= vv[a];
		vv[a]= this; i=a; j=b; next= p;
	}
}e[MAXV*20], *v[MAXV], *vr[MAXV];
void dfs(int now){
	vst[now]= 1;
	for(edge *p=v[now]; p; p=p->next)
		if(!vst[p->j])
			dfs(p->j);
	stamp= now; ++tt;
}
void dfsr(int now){
	vst[now]= 1; ++cnt;
	for(edge *p=v[now]; p; p=p->next)
		if(!vst[p->j])
			dfsr(p->j);
}
int dfs3(int now){
	int t;
	vst[now]= _tar;
	for(edge *p=v[now],*q=NULL; p; p=p->next){
		if(vst[p->j]== _tar){
			eCnt++;
			if(q)q->next= p->next;
			else v[now]= p->next;
			return p->j;
		}
		else{
			t= dfs3(p->j);
			if(t!=0){
				eCnt++;
				if(q){q->next= p->next;}
				else v[now]= p->next;
				if(t!=now){
					return t;
				}
			}else q=p;
		}
	}
	return 0;
}
int main(){
	scanf("%d", &T);
	while(T--){
		scanf("%d%d", &n, &m);
		//init
		for(int i=0; i<=n; i++){
			vst[i]= 0;
			v[i]= vr[i]= NULL;
		}
		can= 1; tt= cnt= eCnt= 0;
		//input
		for(int i=0; i<m; i++){
			scanf("%d%d", &a, &b); ++a; ++b;
			e[i].set(a, b, v);
			e[i+m].set(b, a, vr);
		}
		//dfs
		dfs(1);
		if(tt!= n){puts("NO"); continue;}
		for(int i=1; i<=n; i++) vst[i]= 0;
		dfsr(stamp);
		if(cnt!= n){puts("NO"); continue;}
		for(int i=1; i<=n; i++) vst[i]= 0;
		for(int i=1; i<=n; i++){
			_tar= i;
			dfs3(i);
		}
		puts(eCnt== m? "YES": "NO");
	}
}