记录编号	103382	评测结果	AA
题目名称	1648.[IPSC2003]到根了吗？	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.127 s
提交时间	2014-05-27 20:23:03	内存使用	3.27 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=50010;//点数范围,也是边数范围
int N,M;
int T;
class EDGE{
public:
	int to;
	int id;
};
vector<EDGE> c[SIZEN];
vector<int> tree[SIZEN];
pair<int,int> edges[SIZEN];
bool isbridge[SIZEN];
bool visit[SIZEN]={0};
int father[SIZEN]={0};//来的边,有重边的Tarjan真是一个奇怪的玩意......
int dfn[SIZEN]={0},low[SIZEN]={0};
int timer;
int tot;
int comp[SIZEN]={0};
int edgenum[SIZEN]={0};
int compsg[SIZEN]={0};
int SG[SIZEN]={0};
void Tarjan(int x){
	visit[x]=true;//无向图没有横叉边
	dfn[x]=low[x]=++timer;
	for(int i=0;i<c[x].size();i++){
		int v=c[x][i].to;
		if(!visit[v]){
			father[v]=c[x][i].id;
			Tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		else if(c[x][i].id!=father[x]) low[x]=min(low[x],dfn[v]);
		if(dfn[x]<low[v]) isbridge[c[x][i].id]=true;
	}
}
void DFS(int x){//给每个联通块标号
	visit[x]=true;
	comp[x]=tot;
	for(int i=0;i<c[x].size();i++){
		int v=c[x][i].to;
		if(isbridge[c[x][i].id]||visit[v]) continue;
		DFS(v);
	}
}
void searchedge(void){//统计每块有多少边,顺便建树
	for(int i=1;i<=M;i++){
		int a=edges[i].first,b=edges[i].second;
		if(!isbridge[i]&&comp[a]==comp[b]){
			edgenum[comp[a]]++;
		}
		if(comp[a]!=comp[b]){
			tree[comp[a]].push_back(comp[b]);
			tree[comp[b]].push_back(comp[a]);
		}
	}
}
int DP(int x){
	visit[x]=true;
	int &ans=SG[x];
	for(int i=0;i<tree[x].size();i++){
		if(!visit[tree[x][i]]){
			ans^=(DP(tree[x][i])+1);
		}
		else if(tree[x][i]==x) ans^=1;
	}
	return ans;
}
void work(void){
	Tarjan(1);
	memset(visit,0,sizeof(visit));
	for(int i=1;i<=N;i++) if(!visit[i]) tot++,DFS(i);
	searchedge();
	for(int i=1;i<=tot;i++) SG[i]=edgenum[i]&1;//算了两次
	memset(visit,0,sizeof(visit));
	if(DP(comp[1])) printf("Alice\n");
	else printf("Bob\n");
}
void globalclear(void){
	for(int i=0;i<SIZEN;i++) c[i].clear();
	for(int i=0;i<SIZEN;i++) tree[i].clear();
	memset(isbridge,0,sizeof(isbridge));
	timer=0;
	tot=0;
	memset(visit,0,sizeof(visit));
	memset(edgenum,0,sizeof(edgenum));
	memset(SG,0,sizeof(SG));
}
void read(void){
	scanf("%d%d",&N,&M);
	globalclear();
	int a,b;
	for(int i=1;i<=M;i++){
		scanf("%d%d",&a,&b);
		edges[i]=make_pair(a,b);
		c[a].push_back((EDGE){b,i});
		c[b].push_back((EDGE){a,i});
	}
}
int main(){
	freopen("gotroot.in","r",stdin);
	freopen("gotroot.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		read();
		work();
	}
	return 0;
}